#include "gondola.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
int valid(int n, int inputSeq[])
{
set<int> s;
int num=-1;
for(int i=0;i<n;i++){
if(s.find(inputSeq[i])!=s.end())return 0;
s.insert(inputSeq[i]);
int cur=(inputSeq[i]-i < 0 ? inputSeq[i]-i+n:inputSeq[i]-i);
if(inputSeq[i] <= n){
if(num == -1){
num=cur;
}
else {
if(num!=cur){
return 0;
}
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<pair<int,int>> t;
int st=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<=n){
int one=(i-gondolaSeq[i]+1);
if(one < 0)one+=n;
st=one;
break;
}
}
for(int i=0, j=st;i<n;i++){
t.push_back({i+1, gondolaSeq[(i+j)%n]});
}
sort(t.begin(),t.end(), [&](auto a, auto b){
return a.s<b.s;
});
assert((int)t.size()==n);
int ind=0;
for(int i=0;i<n;i++){
if(t[i].f==t[i].s)continue;
replacementSeq[ind++]=t[i].f;
int prv;
if(i==0)prv=n;
else prv=max(t[i-1].s, n);
for(int j=prv+1;j<t[i].s;j++){
replacementSeq[ind++]=j;
}
}
return ind;
}
//----------------------
const int mod=1000000009;
int exp(int x, int k){
if(k==0)return 1;
if(k==1)return x;
int res=exp(x, k/2);
return res*res%mod*(x % 2 == 0? 1:x)%mod;
}
int countReplacement(int n, int gondolaSeq[])
{
vector<pair<int,int>> t;
int st=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<=n){
int one=(i-gondolaSeq[i]+1);
if(one < 0)one+=n;
st=one;
break;
}
}
for(int i=0, j=st;i<n;i++){
t.push_back({i+1, gondolaSeq[(i+j)%n]});
}
sort(t.begin(),t.end(), [&](auto a, auto b){
return a.s<b.s;
});
assert((int)t.size()==n);
if(!valid(n, gondolaSeq))return 0;
int ans=1;
for(int i=0;i<n;i++){
if(t[i].f==t[i].s)continue;
int prv;
if(i == 0)prv=n;
else prv=max(n, t[i-1].s);
int x=t[i].s-prv-1;
ans=ans*exp(n-i, x)%mod;
//~ ans=ans*exp(n-i, x)%mod;
}
return ans;
}
