#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
int valid(int n, int a[])
{
set<int>s;
vector<int>p,rep;
fore(i,0,n){
if(s.count(a[i]))return 0;
s.insert(a[i]);
if(a[i]<=n){
p.pb(a[i]);
}else{
rep.pb(a[i]);
}
}
int nn=SZ(p);
pair<int,int>ini={1e9,1e9};
fore(i,0,nn){
ini=min(ini,{p[i],i});
}
int j=ini.snd;
fore(i,0,nn){
if(i<nn-1){
if(p[j]>=p[(j+1)%nn]){
return 0;
}
}
j=(j+1)%nn;
}
return 1;
}
int replacement(int n, int a[], int res[])
{
int f=-1;
fore(i,0,n){
if(a[i]<=n){
f=i;
break;
}
}
vector<pair<int,int>>t;
if(f==-1){
t.pb({1,a[0]});
f=0;
a[0]=1;
}
fore(i,f+1,n){
if(a[i]>n){
t.pb({a[(i-1+n)%n]%n+1,a[i]});
a[i]=a[(i-1+n)%n]%n+1;
}
}
fore(i,0,f){
if(a[i]>n){
t.pb({a[(i-1+n)%n]%n+1,a[i]});
a[i]=a[(i-1+n)%n]%n+1;
}
}
sort(ALL(t),[&](auto &a,auto &b){
return a.snd<b.snd;
});
int cur=n+1,op=0;
fore(i,0,SZ(t)){
int ori=t[i].fst,tar=t[i].snd;
while(ori<tar){
res[op++]=ori;
ori=cur++;
}
}
return op;
}
const int MOD=1e9+9;
ll exp(ll a,ll b){
if(b==0)return 1;
ll tmp=exp(a,b/2);
tmp*=tmp;
tmp%=MOD;
if(b%2)tmp*=a;
tmp%=MOD;
return tmp;
}
int countReplacement(int n, int a[])
{
if(valid(n,a)==0)return 0;
vector<int>v;
fore(i,0,n){
if(a[i]>n){
v.pb(a[i]);
}
}
sort(ALL(v));
ll ans=1;
int cur=n,tam=SZ(v);
fore(i,0,SZ(v)){
int diff=v[i]-cur-1;
ans=(ans*exp(tam--,diff))%MOD;
cur=v[i];
}
if(SZ(v)==n)ans*=n;
ans%=MOD;
return ans;
}
