#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define dbg(x) cout << "[ " << #x << " ] : " << x<<endl;
#define F first
#define S second
const int mod=1e9+9;
#define all(v) v.begin(),v.end()
#define ll long long
ll binpow(ll a,ll b){
ll res=1;
while(b>0){
if(b&1) res=(res%mod*a%mod)%mod;
b>>=1;
a=(a%mod*a%mod)%mod;
}
return res;
}
const int INF=1e6;
vector<int> get_sequence(int n,vector<int> v){
for(int i=0;i<n-1;i++){
if(v[i]>v[i+1]){
if(v[i]>n&&v[i+1]<=n){
v[i]=(v[i+1]-2+n)%n+1;
continue;
}
}
if(v[i]<v[i+1]&&v[i+1]>n&&v[i]<=n){
v[i+1]=v[i]%n+1;
}
}
for(int i=n-2;i>=0;i--){
if(v[i]>v[i+1]){
if(v[i]>n&&v[i+1]<=n){
v[i]=(v[i+1]-2+n)%n+1;
continue;
}
}
}
for(int i=0;i<n-1;i++){
if(v[i]>v[i+1]){
if(v[i]>n&&v[i+1]<=n){
v[i]=(v[i+1]-2+n)%n;
continue;
}
}
if(v[i]<v[i+1]&&v[i+1]>n&&v[i]<=n){
v[i+1]=v[i]%n+1;
}
}
for(int i=n-2;i;i--){
if(v[i]>v[i+1]){
if(v[i]>n&&v[i+1]<=n){
v[i]=(v[i+1]-2+n)%n;
continue;
}
}
if(v[i]<v[i+1]&&v[i+1]>n&&v[i]<=n){
v[i+1]=v[i]%n+1;
}
}
for(int i=0;i<n-1;i++){
if(v[i]>v[i+1]){
if(v[i]>n&&v[i+1]<=n){
v[i]=(v[i+1]-2+n)%n;
continue;
}
}
if(v[i]<v[i+1]&&v[i+1]>n&&v[i]<=n){
v[i+1]=v[i]%n+1;
}
}
bool ok=true;
for(int i=0;i<n;i++) ok&=v[i]>n;
if(ok){
v[n-1]=1;
return get_sequence(n,v);
}
return v;}
int valid(int n,int arr[]){
vector<int> v;
for(int i=0;i<n;i++) v.push_back(arr[i]);
set<int> s;
set<int> ss;
for(int i=0;i<n;i++) ss.insert(arr[i]);
v=get_sequence(n,v);
int index=0;
for(int i=0;i<n-1;i++){
if(v[i]<=v[i+1]) index=i+1;
else{
index=i+1;
break;
}
}
bool ok=true;
for(int i=index;i<n-1;i++){
ok&=(v[i]<=v[i+1]);
}
for(int i=0;i<index-1;i++){
ok&=v[i]<=v[i+1];
}
for(int i=0;i<n;i++) s.insert(v[i]);
ok&=(s.size()==n&&ss.size()==n);
return ok;}
int replacement(int n, int arr[], int replacementSeq[]){
vector<int> v;
for(int i=0;i<n;i++) v.push_back(arr[i]);
vector<int> vv=get_sequence(n,v);
set<pair<int,int>> s;
for(int i=0;i<n;i++){
if(v[i]>n) s.insert({v[i],i});
}
vector<int> c;
int start=n+1;
for(auto it=s.begin();it!=s.end();it++){
int f=0;
while(start<=(*it).F) {
if(f==0) c.push_back(vv[(*it).S]);
else{
c.push_back(start);
start++;
}
if(start==(*it).F) break;
f++;
}
start++;
}
for(int i=0;i<c.size();i++) replacementSeq[i]=c[i];
return c.size();}
int countReplacement(int n, int arr[]){
bool x=valid(n,arr);
if(x==false) return 0;
vector<int> v;
for(int i=0;i<n;i++) v.push_back(arr[i]);
vector<int> vv;
// OVL(v," ")
for(int i=0;i<n;i++){
if(v[i]>n) vv.push_back(v[i]);
}
vector<int> c=get_sequence(n,v);
bool ok=true;
set<int> s;
// OVL(c," ")
//check wach no solutions exists first
for(int i=0;i<n;i++){ ok&=(c[i]<=n&&s.find(c[i])==s.end());s.insert(c[i]);}
// dbg(ok);
// if(!ok) return 0;
sort(all(vv));
sort(all(v));
OVL(vv," ")
ll ans=1;
ll lst=n;
for(int i=0;i<vv.size();i++){
ans=(ans%mod*binpow(vv.size()-i,vv[i]-lst-1)%mod)%mod;
ans%=mod;
if(ans>=mod) ans-=mod;
if(ans<0) ans+=mod;
lst=vv[i];
}
if(ans>=mod) ans-=mod;
if(ans<0) ans+=mod;
if(vv.size()==n) {
ans=(ans*n)%mod;
}
if(ans<0) ans+=mod;
if(ans>=mod) ans-=mod;
return (int)(ans%mod);
}
// int gondolaSequence[100001];
// int replacementSequence[250001];
// int main() {
// int i, n, tag;
// int nr;
// assert(scanf("%d", &tag) == 1);
// assert(scanf("%d", &n) == 1);
// for (i = 0; i < n; i++)
// assert(scanf("%d", &gondolaSequence[i]) == 1);
// switch (tag) {
// case 1:
// case 2:
// case 3:
// printf("%d\n", valid(n, gondolaSequence));
// break;
// case 4:
// case 5:
// case 6:
// nr = replacement(n, gondolaSequence, replacementSequence);
// printf("%d ", nr);
// if (nr > 0) {
// for (i = 0; i < nr - 1; i++)
// printf("%d ", replacementSequence[i]);
// printf("%d\n", replacementSequence[nr - 1]);
// } else
// printf("\n");
// break;
// case 7:
// case 8:
// case 9:
// case 10:
// printf("%d\n", countReplacement(n, gondolaSequence));
// break;
// }
// return 0;
// }
