#include "gondola.h"
#include <bits/stdc++.h>
//💖
using namespace std;
typedef long long ll;
ll MOD=1000000009;
bool check[2500050];
int zamena[100];
map<int, int>convent;
vector<int>ord;
int valid(int n, int* inputSeq)
{
int last=-1, pos=-1;
for(int i=0; i<n; i++)
{
if(inputSeq[i]<=n and last==-1){last=inputSeq[i]; pos=i;}
else if(inputSeq[i]<=n)
{
if((last+i-pos)%n==(inputSeq[i])%n){last=inputSeq[i]; pos=i;}
else {return 0;}
}
else if(check[inputSeq[i]])return 0;
check[inputSeq[i]]=true;
}
return 1;
}
int replacement(int n, int* gondolaSeq, int* replacementSeq)
{
int maks=-1, g=-1, k=1;
for(int i=0; i<n; i++)
{
//cout<<gondolaSeq[i]<<" "<<n<<endl;
if(gondolaSeq[i]>n)
{
convent[gondolaSeq[i]]=i+1;
if(gondolaSeq[i]>maks){maks=gondolaSeq[i]; g=i;}
}
else {k=i;}
}
for(int i=0; i<n; i++)
{
gondolaSeq[i]=(gondolaSeq[k]+i-k+n)%n;
if(gondolaSeq[i]==0)gondolaSeq[i]=n;
}
if (maks==-1)return 0;
for(int i=n+1; i<=maks; i++)
{
if(convent[i]==0){replacementSeq[i-n-1]=gondolaSeq[g]; gondolaSeq[g]=i;}
else{replacementSeq[i-n-1]=gondolaSeq[convent[i]-1]; gondolaSeq[convent[i]-1]=i;}
}
return maks-n;
}
int countReplacement(int n, int* inputSeq)
{
int last=-1, pos=-1;
for(int i=0; i<n; i++)
{
if(inputSeq[i]<=n and last==-1){last=inputSeq[i]; pos=i;}
else if(inputSeq[i]<=n)
{
if((last+i-pos)%n==(inputSeq[i])%n){last=inputSeq[i]; pos=i;}
else {return 0;}
}
else if(check[inputSeq[i]])return 0;
check[inputSeq[i]]=true;
}
int cnt=0;
ll maks=0;
for(int i=0; i<n; i++)
{
if(inputSeq[i]>n)
{
cnt++; ord.push_back(inputSeq[i]);
if(inputSeq[i]>maks){maks=inputSeq[i];}
}
}
sort(ord.begin(), ord.end());
ll res=1, pp=0;
ord.push_back(0);
for(int i=n+1; i<=maks; i++)
{
if(i==ord[pp])pp++;
else
{
res=(res*(ord.size()-pp-1))%MOD;
}
}
if(pp==n)res=(res*n)%MOD;
return res;
}
/*int main()
{
int n; cin>>n;
int gondole[n];
for(int i=0; i<n; i++)cin>>gondole[i];
cout<<countReplacement(n, gondole)<<endl;
//for(int i=0; i<11; i++)cout<<zamena[i]<<" ";
}*/
