#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include "gondola.h"
#define MOD 1000000009
int poz[100010];
bool e[250010];
int valid(int n, int inputSeq[])
{
for(int i=0;i<=n;++i)
{
if(e[inputSeq[i]])
return 0;
e[inputSeq[i]]=true;
if(1<=inputSeq[i]&&inputSeq[i]<=n)
poz[inputSeq[i]]=i+1;
}
int dif=-1;
for(int i=1;i<=n;++i)
if(poz[i])
{
int val;
if(i<=poz[i])
val=poz[i]-i;
else
val=poz[i]+n-i;
if(dif==-1)
dif=val;
else if(dif!=val)
return 0;
}
return 1;
}
//----------------------
int ago[100010];
int truevalue(int val,int n)
{
while(val<=0)
val+=n;
return val;
}
int goodshift(int n,int gondolaSeq[])
{
int ls=-1;
for(int i=0;i<n;++i)
if(1<=gondolaSeq[i]&&gondolaSeq[i]<=n)
{
if(gondolaSeq[i]<=i+1)
ls=i+1-gondolaSeq[i];
else
ls=i+1+n-gondolaSeq[i];
break;
}
if(ls==-1)
{
for(int i=0;i<n;++i)
ago[i+1]=gondolaSeq[i];
return 0;
}
for(int i=0;i<n;++i)
ago[truevalue(i+1-ls,n)]=gondolaSeq[i];
return 1;
}
int pozval[250010],valac;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
goodshift(n,gondolaSeq);
for(int i=1;i<=n;++i)
pozval[ago[i]]=i;
valac=n;
for(int i=1;i<=n;++i)
ago[i]=i;
for(int i=n+1;i<=250000;++i)
{
if(pozval[i]!=0)
{
while(valac<i)
{
replacementSeq[valac-n]=ago[pozval[i]];
++valac;
ago[pozval[i]]=valac;
}
}
}
return valac-n;
}
//----------------------
long long ans=1;
long long putere(long long a,long long b)
{
if(b==0)
return 1;
long long m=putere(a,b/2);
m*=m;
m%=MOD;
if(b%2)
{
m*=a;
m%=MOD;
}
return m;
}
int countReplacement(int n, int inputSeq[])
{
if(valid(n,inputSeq)==0)
return 0;
std::sort(inputSeq,inputSeq+n);
if(inputSeq[0]>n)
ans*=n;
int poz=0;
while(poz<n&&inputSeq[poz]<=n)
++poz;
if(poz!=0)
inputSeq[poz-1]=n;
for(;poz<n;++poz)
{
if(poz==0)
ans*=putere(n-poz,inputSeq[poz]-n-1);
else
ans*=putere(n-poz,inputSeq[poz]-inputSeq[poz-1]-1);
ans%=MOD;
}
return ans;
}
