//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "gondola.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
int valid(int n, int arr[])
{
for(int i = 0; i< n; i++) arr[i]--;
vi vec;
for(int i = 0; i< n; i++) vec.pb(arr[i]);
sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end())-vec.begin());
if(vec.size() != n) return 0;
vi tmp;
for(int i = 0; i< n; i++) if(arr[i]< n) tmp.pb((arr[i]-i+n)%n);
sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end())-tmp.begin());
return (tmp.size()<= 1);
}
int replacement(int n, int arr[], int ans[])
{
for(int i = 0; i< n; i++) arr[i]--;
vi tmp;
for(int i = 0; i< n; i++) if(arr[i]< n) tmp.pb((arr[i]-i+n)%n);
sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end())-tmp.begin());
int q = tmp.size();
int st = q?tmp[0]:0;
vii strange;
for(int i = 0; i< n; i++) if(arr[i]>= n) strange.pb(ii(arr[i], (i+st)%n));
sort(strange.begin(), strange.end());
int ptr = 0;
for(int i = 0; i< strange.size(); i++)
{
//printf("%d %d\n", strange[i].X, strange[i].Y);
int prv = i?strange[i-1].X:n-1;
int rounds = strange[i].X-prv;
rounds--;
ans[ptr++] = strange[i].Y+1;
while(rounds--)
{
ans[ptr] = n+ptr;
ptr++;
}
}
return ptr;
}
//----------------------
const int md = 1e9+9;
int mul(int a, int b)
{
return (1LL*a*b)%md;
}
int ninja(int a, int b)
{
if(b == 0) return 1;
int x = ninja(a, b/2);
int y = mul(x, x);
if(b%2) y = mul(y, a);
return y;
}
int countReplacement(int n, int arr[])
{
if(!valid(n, arr)) return 0;
vi tmp;
for(int i = 0; i< n; i++) if(arr[i]< n) tmp.pb((arr[i]-i+n)%n);
sort(tmp.begin(), tmp.end()); tmp.resize(unique(tmp.begin(), tmp.end())-tmp.begin());
int q = tmp.size();
int st = q?tmp[0]:0;
vii strange;
for(int i = 0; i< n; i++) if(arr[i]>= n) strange.pb(ii(arr[i], (i+st)%n));
sort(strange.begin(), strange.end());
int ptr = 0;
int res = 1;
for(int i = 0; i< strange.size(); i++)
{
//printf("%d %d\n", strange[i].X, strange[i].Y);
int prv = i?strange[i-1].X:n-1;
int rounds = strange[i].X-prv;
rounds--;
//printf("pow %d %d\n", strange.size()-i, rounds);
res = mul(res, ninja(strange.size()-i, rounds));
}
if(!q) res = mul(res, strange.size());
return res;
}
