#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
const long long MOD=1000000007;
long long powe(long long a, long long b){
long long ans=1;
a%=MOD;
while(b>0){
if(b%2==1){
ans=(ans*a)%MOD;
}
a=(a*a)%MOD;
b/=2;
}
return ans;
}
int valid(int n, int inputSeq[])
{
unordered_set<int> se;
int d=-1, s=-1;
for(int i=0; i<n; i++){
if(se.count(inputSeq[i])==true){
return 0;
}
se.insert(inputSeq[i]);
if(inputSeq[i]<=n and d==-1){
d=i;
s=inputSeq[i];
}
}
if(d==-1){
return 1;
}
for(int i=0; i<n; i++){
if(inputSeq[i]<=n){
int ex=(s-1+(i-d))%n;
if(ex<0){
ex+=n;
}
ex+=1;
if(inputSeq[i]!=ex){
return 0;
}
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int f=-1;
for(int i=0; i<n; i++){
if(gondolaSeq[i]<=n){
f=i;
}
}
int s=1;
if(f!=-1){
s=(gondolaSeq[f]-f+n-1)%n+1;
}
vector<pair<int, int> > p;
for(int i=0; i<n; i++){
if(gondolaSeq[i]>n){
int og=(s+i-1)%n+1;
p.push_back({gondolaSeq[i], og});
}
}
sort(p.begin(), p.end());
int cur=n+1;
int id=0;
for(auto u : p){
int t=u.first;
int sr=u.second;
while(sr<t){
replacementSeq[id++]=sr;
sr=cur++;
}
}
return id;
}
int countReplacement(int n, int inputSeq[])
{
if(valid(n, inputSeq)==0){
return 0;
}
vector<int> r;
bool f=false;
for(int i=0; i<n; i++){
if(inputSeq[i]>n){
r.push_back(inputSeq[i]);
}else{
f=true;
}
}
sort(r.begin(), r.end());
long long ans=1;
if(f==false){
ans=n;
}
int l=n;
for(int i=0; i<(int)r.size(); i++){
int ch=(int)r.size()-i;
ans=(ans*powe(ch, r[i]-l-1))%MOD;
l=r[i];
}
return (int)ans;
}
