#include<bits/stdc++.h>
using namespace std;
const int INF=1123456789,MAXN=250010,MOD=1000000009,MAXL=32;
#define debug(args...) //fprintf(stderr,args)
map<int,int> vld;
int marc[MAXN];
#include "gondola.h"
int valid(int n,int seq[])
{
int mn=INF,at=INF,at2=INF,id0=0;
int st=0;
bool vl=1;
for(int i=0;i<n;i++)
{
if(vl==0)debug("%d\n",i);
if(vld[seq[i]]>0)vl=0;
vld[seq[i]]++;
if(st==0)
{
if(seq[i]>n)continue;
if(seq[i]<at && at==INF)
{
at=seq[i];mn=seq[i];
id0=(i+1-mn+n)%n;
}
else if(seq[i]<at)
{
at2=seq[i];st=1;
if(at2>mn)vl=0;
}
else
{
if((id0+seq[i]-1)%n!=i)vl=0;
at=seq[i];
}
}
else
{
if(seq[i]>n)continue;
if(seq[i]<at2 || seq[i]>mn || seq[i]>at)vl=0;
if((id0+seq[i]-1)%n!=i)vl=0;
at2=seq[i];
}
debug("%d %d %d\n",i,id0,(id0+seq[i])%n);
}
return vl;
}
int replacement(int n,int seq[],int replacementseq[])
{
vector<pair<int,int> > v;
int mn=INF,at=INF,at2=INF,id0=0,mx=0,imx=0;
int st=0;
bool vl=1;
for(int i=0;i<n;i++)
{
marc[seq[i]]=1;
if(mx<seq[i])imx=i;
mx=max(mx,seq[i]);
if(vl==0)debug("%d\n",i);
if(vld[seq[i]]>0)vl=0;
vld[seq[i]]++;
if(st==0)
{
if(seq[i]>n)continue;
if(seq[i]<at && at==INF)
{
at=seq[i];mn=seq[i];
id0=(i+1-mn+n)%n;
}
else if(seq[i]<at)
{
at2=seq[i];st=1;
if(at2>mn)vl=0;
}
else
{
if((id0+seq[i]-1)%n!=i)vl=0;
at=seq[i];
}
}
else
{
if(seq[i]>n)continue;
if(seq[i]<at2 || seq[i]>mn || seq[i]>at)vl=0;
if((id0+seq[i]-1)%n!=i)vl=0;
at2=seq[i];
}
debug("%d %d %d\n",i,id0,(id0+seq[i])%n);
}
int cnt=0,lst=(imx-id0+n)%n+1;
for(int i=0;i<n;i++)if(seq[i]>n && seq[i]!=mx)replacementseq[seq[i]-n-1]=(i-id0+n)%n+1;
for(int i=n+1;i<mx;i++)
{
if(!marc[i] && cnt==0)
{
replacementseq[i-n-1]=(imx-id0+n)%n+1;
cnt=1;
lst=i;
}
else if(!marc[i])
{
replacementseq[i-n-1]=lst;
lst=i;
}
}
for(int i=0;i<n;i++)if(seq[i]==mx)replacementseq[mx-n-1]=lst;
//for(int i=0;i<mx-n;i++)printf("%d ",replacementseq[i]);
//printf("\n");
return mx-n;
}
long long fst_exp(long long n,int k)
{
long long val=n;
long long resp=1;
for(int i=MAXL-1;i>=0;i--)
{
resp*=resp;
if(k&(1<<i))resp*=val;
if(resp>MOD)resp=resp%MOD;
}
return resp;
}
long long fat(long long n)
{
if(n==1)return 1;
else return (n*fat(n-1))%MOD;
}
int countReplacement(int n1,int seq[])
{
long long n=(long long)n1;
debug("%lld\n",n);
vector<int> v;
int mn=INF,at=INF,at2=INF,id0=0,mx=0,imx=0;
int st=0;
bool vl=1;
for(int i=0;i<n;i++)
{
if(seq[i]>n)v.push_back(seq[i]);
if(mx<seq[i])imx=i;
mx=max(mx,seq[i]);
if(vl==0)debug("%d\n",i);
if(vld[seq[i]]>0)vl=0;
vld[seq[i]]++;
if(id0==0)
{
if(seq[i]>n)continue;
id0=(seq[i] - i + n)%n;
st = 1;
}
else
{
if(seq[i]>n)continue;
if((seq[i] - i + n) % n != id0) vl = 0;
}
}
if(vl==0)return vl;
sort(v.begin(),v.end());
long long resp=1;
int cnt=0,lst=n;
for(int i=0;i<v.size();i++)
{
resp*=fst_exp((long long)v.size()-i,v[i]-lst-1);
//printf("%lld %d %d %d %d\n",resp,v.size()-i,v[i]-lst-1,v[i],lst);
if(resp>MOD)resp%=MOD;
lst=v[i];
}
long long k1=n;
if(v.size()==n)resp*=k1;
if(v.size()==0)resp=1;
resp%=MOD;
//for(int i=0;i<mx-n;i++)printf("%d ",replacementseq[i]);
//printf("\n");
return resp;
}
/*int v[1123456];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&v[i]);
printf("%d\n",countReplacement(n,v));
return 0;
}*/
