#include "gondola.h"
#include<algorithm>
#include<map>
#include<string.h>
using namespace std;
map<int,int>visit2;
int a[100010],ch[250010],visit[250010];
long long int sav[50],sav2[50];
struct data
{
int x,y;
bool operator<(const data&r)const
{
return x<r.x;
}
}arr[250010];
int valid(int n, int inputSeq[])
{
int i,k=0;
for(i=0;i<n;i++)
{
if(visit[inputSeq[i]]==1) return 0;
visit[inputSeq[i]]=1;
if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1;
}
for(i=1;i<=n;i++)
{
if(ch[i]!=0 && k==0)
{
k=ch[i];
continue;
}
if(k!=0)
{
k++;
if(k>n) k=1;
}
if(ch[i]!=0 && k!=ch[i]) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int s,i,big=0,k=1,w=0,top=0,pos=0,p=0;
for(i=0;i<n;i++)
{
ch[gondolaSeq[i]]=1;
if(gondolaSeq[i]<=n) visit[i]=1;
if(big<gondolaSeq[i]) big=gondolaSeq[i];
if(gondolaSeq[i]<=n) pos=i,p=gondolaSeq[i];
}
for(i=0;i<n;i++)
{
if(visit[i]==0)
{
top++;
arr[top].x=gondolaSeq[i];
arr[top].y=i;
}
}
sort(arr+1,arr+top+1);
if(p==0)
{
for(i=0;i<n;i++) a[i]=i+1;
}
else
{
for(i=pos;i<=pos+n-1;i++)
{
a[i%n]=p;
p++;
if(p==n+1) p=1;
}
}
for(i=n+1;i<=big;i++)
{
if(ch[i]==0)
{
replacementSeq[w++]=a[arr[k].y];
a[arr[k].y]=i;
}
else
{
replacementSeq[w++]=a[arr[k].y];
a[arr[k].y]=i;
k++;
}
}
return w;
}
//----------------------
long long int f(long long int c,int k)
{
int i,t=0;
long long int gap=1;
sav[1]=c;
for(i=2;i<=50;i++)
{
sav[i]=sav[i-1]*sav[i-1];
sav[i]%=1000000009;
}
while(k>0)
{
sav2[++t]=k%2;
k/=2;
}
for(i=1;i<=t;i++)
{
if(sav2[i]==1)
{
gap*=sav[i]; gap%=1000000009;
}
}
return gap;
}
int countReplacement(int n, int inputSeq[])
{
int s,i,big=0,k=0,w=0,top=0,pos=0,p=0,r=0;
long long int dap=1,c;
for(i=0;i<n;i++)
{
if(visit2[inputSeq[i]]==1) return 0;
visit2[inputSeq[i]]=1;
if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1;
}
for(i=1;i<=n;i++)
{
if(ch[i]!=0 && k==0)
{
k=ch[i];
continue;
}
if(k!=0)
{
k++;
if(k>n) k=1;
}
if(ch[i]!=0 && k!=ch[i]) return 0;
}
k=1;
memset(ch,0,sizeof ch);
for(i=0;i<n;i++)
{
if(inputSeq[i]>n) ch[++r]=inputSeq[i];
if(inputSeq[i]<=n) visit[i]=1;
if(big<inputSeq[i]) big=inputSeq[i];
if(inputSeq[i]<=n) pos=i,p=inputSeq[i];
}
for(i=0;i<n;i++)
{
if(visit[i]==0)
{
top++;
arr[top].x=inputSeq[i];
arr[top].y=i;
}
}
sort(arr+1,arr+top+1);
sort(ch+1,ch+r+1);
if(p==0)
{
for(i=0;i<n;i++) a[i]=i+1;
dap=n;
}
else
{
for(i=pos;i<=pos+n-1;i++)
{
a[i%n]=p;
p++;
if(p==n+1) p=1;
}
}
c=top;
ch[0]=n;
for(i=1;i<=r;i++)
{
dap*=f(c,ch[i]-ch[i-1]-1);
dap%=1000000009;
c--;
}
return dap;
}
