#include "gondola.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
typedef long long ll;
using namespace std;
signed valid(signed n, signed 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;
}
//----------------------
signed replacement(signed N, signed gondolaSeq[], signed replacementSeq[])
{
long long n=N;
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 ll mod=1000000009;
ll exp(ll x, ll k){
if(k==0)return 1;
if(k==1)return x % mod;
ll res=exp(x, k/2);
if(k%2==0)return res * res % mod;
else return res * res %mod * x %mod;
}
signed countReplacement(signed N, signed gondolaSeq[])
{
int n=N;
//~ cout<<exp(3, 78)<<"\n";
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;
ll 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;
//~ printf("dist %lld, choices %lld\n", x, n-i);
ans=ans*exp(n-i, x)%mod;
//~ ans=ans*exp(n-i, x)%mod;
}
return ans;
}
