#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000009;
int n,m,b[li],k,t,c[li];
lo cev,flag=-1;
string s;
vector<lo> v;
int valid(int n, int a[]){
for(int i=0;i<n;i++)b[i]=a[i];
sort(b,b+n);
for(int i=1;i<n;i++){
if(b[i]==b[i-1])return 0;
}
for(int i=0;i<n;i++){
if(a[i]<=n){
//~ cout<<a[i]-i<<endl;
lo at=0;
if(a[i]>i+1)at=i+1+(n-a[i]);
else at=(i+1)-a[i];
//~ cout<<at<<endl;
if(flag==-1){
flag=at;
}
else{
if(flag!=at)return 0;
}
}
}
return 1;
}
int replacement(int n, int a[], int replacementSeq[]){
int mx=0,ind=0,yes=0;
memset(b,-1,sizeof(b));
for(int i=0;i<n;i++){
if(a[i]>mx)ind=i;
mx=max(mx,a[i]);
b[a[i]]=i;
if(a[i]<=n)yes=i;
}
int len=0;
int say=a[yes];
if(say>n)say=1;
for(int i=yes;i<n;i++){
c[i]=(say);
say++;
say=say%(n+1);
if(say==0)say=1;
}
for(int i=0;i<yes;i++){
c[i]=(say);
say++;
say=say%(n+1);
if(say==0)say=1;
}
//~ cout<<yes<<endl;
for(int i=n+1;i<=mx;i++){
if(~b[i]){replacementSeq[len++]=c[b[i]];c[b[i]]=i;}
else{replacementSeq[len++]=c[ind];c[ind]=i;}
}
return len;
}
inline lo mul(lo x,lo y){
return (x%mod)*(y%mod)%mod;
}
inline lo fp(lo x,lo y){
if(y==0)return 1;
if(y==1)return x;
lo q=fp(x,y/2);
q=mul(q,q);
if(y%2)q=mul(q,x);
return q;
}
int countReplacement(int n, int a[]){
if(valid(n,a)==0)return 0;
lo carp=n;
//~ lo mx=0;
//~ memset(b,-1,sizeof(b));
for(lo i=0;i<n;i++){
//~ b[a[i]]=1;
if(a[i]<=n)carp--;
else v.pb(a[i]);
}
v.pb(n);
sort(v.begin(),v.end());
cev=1;
if(carp==n)cev=n;
for(lo i=1;i<(lo)v.size();i++){
cev=mul(cev,fp(carp,v[i]-v[i-1]-1));
carp--;
}
return cev;
}
