#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n,int x_[])
{
static int x[100001];
set<int> u;
int s=0;
for(int i=0;i<n;++i)
{
x[i]=x_[i]-1; u.insert(x[i]);
if(x[i]<n) s=(x[i]-i+n)%n;
if(x[i]<0) return 0;
}
if(int(u.size())!=n) return 0;
for(int i=0;i<n;++i)
if(x[i]<n&&(s+i)%n!=x[i]) return 0;
return 1;
}
//----------------------
int replacement(int n, int x_[], int o[])
{
static int x[100001],y[100001];
set<int> em;
map<int,int> t;
int s=0,mx=0;
for(int i=0;i<n;++i)
{
x[i]=x_[i]-1;
t[x[i]]=i; mx=max(mx,x[i]);
if(x[i]<n) s=(x[i]-i+n)%n;
if(x[i]<0) return 0;
}
for(int i=0;i<n;++i)
{
y[i]=(s+i)%n;
if(y[i]!=x[i]) em.insert(i);
}
int on=0;
for(int j=n;j<=mx;++j)
{
int p;
if(t.count(j))
em.erase(p=t[j]);
else p=*em.begin();
o[on++]=y[p]+1; y[p]=j;
}
return on;
}
//----------------------
#define fi first
#define se second
const int MOD=1e9+9;
typedef long long ll;
ll qp(ll a,ll b)
{
ll x=1; a%=MOD;
while(b)
{
if(b&1) x=x*a%MOD;
a=a*a%MOD; b>>=1;
}
return x;
}
int countReplacement(int n, int x_[])
{
if(!valid(n,x_)) return 0;
static int x[100001],y[100001];
map<int,int> sb;
int s=n,mx=0;
for(int i=0;i<n;++i)
{
x[i]=x_[i]-1; mx=max(mx,x[i]);
if(x[i]<n) s=(x[i]-i+n)%n;
if(x[i]<0) return 0;
}
for(int i=0;i<n;++i)
{
y[i]=(s+i)%n;
if(y[i]!=x[i]) sb[x[i]]--;
}
int ini=sb.size();
sb[mx+1]=0;
sb[n-1]+=ini;
ll ans=1;
int su=0;
for(auto t=sb.begin();;++t)
{
if(t->fi>mx) break;
su+=t->se;
auto u=t; ++u;
ans=ans*qp(su,u->fi-t->fi-1)%MOD;
}
if(s==n) ans=ans*(ll)n%MOD;
return ans;
}
