/*input
2
3 4
*/
/**
Author: Kristopher Paul
Date Created: 15-05-2019
Contest Name:
_/ _/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/_/ _/_/_/_/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/_/_/_/
**/
#include <gondola.h>
#include<bits/stdc++.h>
#define ll long long
//#define int ll
#define pb push_back
#define INF 0x3f3f3f3f //0x3f3f3f3f = 63
#define MOD 1000000009
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define umap unordered_map
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define all(v) v.begin(),v.end()
#define WL(t) while(t--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define out(x) cout << #x << " is " << x << endl
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
ll ModExp(ll x,ll y,ll m){
ll res = 1;
x = x % m;
while (y > 0)
{
if (y & 1)
res = (res*x) % m;
y = y>>1;
x = (x*x) % m;
}
return res;
}
int valid(int n, int arr[]){
int mini = n+1;
int pos = n;
umap<int,int> cnt;
FOR(i,0,n){
cnt[arr[i]]++;
if(cnt[arr[i]] > 1){
return 0;
}
if(arr[i] < mini){
mini = arr[i];
pos = i;
}
}
if(mini > n){
return 1;
}
int to[n];
int val = arr[pos];
FOR(i,pos,n){
to[i] = val;
if(arr[i] <= n && arr[i] != to[i]){
return 0;
}
val++;
if(val == n+1){
val = 1;
}
}
FOR(i,0,pos){
to[i] = val;
if(arr[i] <= n && arr[i] != to[i]){
return 0;
}
val++;
if(val == n+1){
val = 1;
}
}
return 1;
}
int replacement(int n, int arr[], int replacementSeq[]){
int mini = n+1;
int pos = 0;
FOR(i,0,n){
if(arr[i] < mini){
mini = arr[i];
pos = i;
}
}
vector<pii> vec;
if(mini > n){
FOR(i,0,n){
vec.pb({arr[i],i+1});
}
}else{
int v = mini;
FOR(i,pos,n){
if(arr[i] > n){
vec.pb({arr[i],v});
}
v++;
if(v == n+1){
v = 1;
}
}
FOR(i,0,pos){
if(arr[i] > n){
vec.pb({arr[i],v});
}
v++;
if(v == n+1){
v = 1;
}
}
}
sort(vec.begin(),vec.end());
int st = n+1;
int ind = 0;
FOR(i,0,vec.size()){
int cur = vec[i].first;
int lv = vec[i].second;
FOR(j,st,cur+1){
replacementSeq[ind] = lv;
lv = j;
ind++;
}
st = cur+1;
}
return ind;
}
int countReplacement(int n, int arr[]){
if(!valid(n,arr)){
return 0;
}
int maxi = 0;
int mini = n+1;
int pos = 0;
FOR(i,0,n){
remax(maxi,arr[i]);
if(arr[i] < mini){
mini = arr[i];
pos = i;
}
}
if(maxi <= n){
return 1;
}
vector<int> vec;
FOR(i,0,n){
if(arr[i] > n){
vec.pb(arr[i]);
}
}
sort(vec.begin(),vec.end());
int st = n+1;
vector<ll> sz;
ll cur = 0;
FOR(i,0,vec.size()){
cur += vec[i]-st;
if(cur > 0){
sz.pb(cur);
}
st = vec[i]+1;
}
ll ans = 1;
int lv = 1;
FOR(i,0,sz.size()){
if(sz[i] < lv){
continue;
}
ans *= ModExp((sz.size()-i),(sz[i]-lv+1),MOD);
ans %= MOD;
lv = sz[i]+1;
}
if(mini > n){
ans *= n;
ans %= MOD;
}
ans %= MOD;
return ans;
}
/*
void solve(){
int n;
cin >> n;
int arr[n];
FOR(i,0,n){
cin >> arr[i];
}
cout << countReplacement(n,arr) << endl;
}
signed main(){
FastIO;
int t = 1;
// cin >> t;
WL(t){
solve();
}
}*/
