#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll MOD=1000000009;
ll safe_mod(ll n,ll p){
n%=p;
if(n<0)n+=p;
return n;
}
int valid(int n, int inputSeq[]){
int fix=MOD;
rep(i,n){
if(inputSeq[i]<=n){
if(fix==MOD)fix=safe_mod(i-inputSeq[i],n);
else{
if(fix!=safe_mod(i-inputSeq[i],n)){
return 0;
}
}
}
}
vector<bool> cnt(300000);
rep(i,n){
if(cnt[inputSeq[i]])return 0;
cnt[inputSeq[i]]=1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int cnt=0;
vector<int> repl(300000,-1);
rep(i,n){
repl[gondolaSeq[i]]=i;
}
int fix=0;
vector<bool> inc(n,0);
rep(i,n){
if(gondolaSeq[i]<=n){
fix=safe_mod(i-gondolaSeq[i],n);
inc[i]=1;
}
}
vector<int> gdls(n);
rep(i,n){
gdls[i]=safe_mod(i-fix,n);
if(gdls[i]==0)gdls[i]=n;
}
int gdl=n+1;
int pos=0;
while(pos<n&&inc[pos])pos++;
while(true){
if(pos==n)break;
if(repl[gdl]==-1){
replacementSeq[cnt]=gdls[pos];
gdls[pos]=gdl;
}
else{
replacementSeq[cnt]=gdls[repl[gdl]];
gdls[repl[gdl]]=gdl;
inc[repl[gdl]]=1;
}
cnt++;
gdl++;
while(pos<n&&inc[pos])pos++;
}
return cnt;
}
//----------------------
ll pow_mod(ll n,ll x){
if(x==0)return 1;
ll ret=pow_mod(n,x/2);
ret=safe_mod(ret*ret,MOD);
if(x&1)ret=safe_mod(ret*n, MOD);
return ret;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)){
return 0;
}
vector<int> broken;
ll ans=n;
int can=n;
rep(i,n){
if(inputSeq[i]<=n){
ans=1;
can--;
}
else{
broken.push_back(inputSeq[i]);
}
}
sort(all(broken));
int now=n;
for(int i:broken){
ans=safe_mod(ans*pow_mod(can, i-now-1), MOD);
can--;
now=i;
}
return ans;
}
