#include "gondola.h"
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
const int MOD=1e9+9;
int modpow(int base,int exp){
int ac=1;
for(;exp>0;exp>>=1){
if(exp&1){
ac=1LL*ac*base%MOD;
}
base=1LL*base*base%MOD;
}
return ac;
}
int valid(int n, int inputSeq[])
{
int shift=-1;
std::set<int> used;
for(int i=0;i<n;i++){
if(used.count(inputSeq[i])) return 0;
used.insert(inputSeq[i]);
if(inputSeq[i]<=n){
int new_shift=(inputSeq[i]-i+n)%n;
if(shift!=-1&&shift!=new_shift) return 0;
shift=new_shift;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i=0;i<n;i++){
gondolaSeq[i]--;
}
int shift=0;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<n){
shift=(gondolaSeq[i]-i+n)%n;
break;
}
}
std::vector<int> seq(n);
for(int i=0;i<n;i++){
seq[i]=(i+shift)%n;
}
auto max=std::max_element(gondolaSeq,gondolaSeq+n);
std::vector<int> where(*max+1,max-gondolaSeq);
for(int i=0;i<n;i++){
where[gondolaSeq[i]]=i;
}
for(int x=n;x<=*max;x++){
replacementSeq[x-n]=seq[where[x]];
seq[where[x]]=x;
}
int l=*max+1-n;
for(int i=0;i<l;i++){
replacementSeq[i]++;
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq)) return 0;
for(int i=0;i<n;i++){
inputSeq[i]--;
}
int shift=-1;
for(int i=0;i<n;i++){
if(inputSeq[i]<n){
shift=(inputSeq[i]-i+n)%n;
break;
}
}
std::set<int> set;
int cnt=(shift==-1)?n:1;
int spots=n;
for(int i=0;i<n;i++){
if(inputSeq[i]<n){
spots--;
}else{
set.insert(inputSeq[i]);
}
}
int prev=n-1;
for(int x:set){
cnt=1LL*cnt*modpow(spots,x-1-prev)%MOD;
prev=x;
spots--;
}
return cnt;
}
