#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#include "gondola.h"
const int mod = 1e9 + 9;
long long fpow(long long a, long long b){
long long p = 1;
while(b){
if(b&1) p = (p * a)%mod;
a = (a * a)%mod;
b /= 2;
}
return p;
}
int valid(int n, int inputSeq[]){
int ind = -1;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n) ind = i;
}
if(ind == -1){
bool ok = 1;
map<int, int> vis;
for(int i = 0; i < n; i++){
if(vis[inputSeq[i]]) ok = 0;
vis[inputSeq[i]] = 1;
}
return ok;
}
vector<int> alternate(n);
for(int i = ind; i < n; i++){
alternate[i] = inputSeq[ind] + (i - ind);
if(alternate[i] > n) alternate[i] -= n;
}
for(int i = 0; i < ind; i++){
alternate[i] = alternate[n-1] + i + 1;
if(alternate[i] > n) alternate[i] -= n;
}
bool ok = 1;
map<int, int> vis;
for(int i = 0; i < n; i++){
if(vis[inputSeq[i]]) ok = 0;
vis[inputSeq[i]] = 1;
if(inputSeq[i] > n || inputSeq[i] == alternate[i]) continue;
ok = 0;
}
return ok;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int l, mx = 0;
int ind = -1;
for(int i = 0; i < n; i++){
mx = max(mx, gondolaSeq[i]);
if(gondolaSeq[i] <= n) ind = i;
}
l = (mx - n);
vector<int> alternate(n);
if(ind == -1){
for(int i = 0; i < n; i++){
alternate[i] = i+1;
}
}
else{
for(int i = ind; i < n; i++){
alternate[i] = gondolaSeq[ind] + (i - ind);
if(alternate[i] > n) alternate[i] -= n;
}
for(int i = 0; i < ind; i++){
alternate[i] = alternate[n-1] + i + 1;
if(alternate[i] > n) alternate[i] -= n;
}
}
vector<pair<int, int> > rep;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] <= n) continue;
rep.pb({gondolaSeq[i], i});
}
sort(rep.begin(), rep.end());
int now = n + 1;
ind = 0;
for(auto itr: rep){
while(itr.first >= now){
replacementSeq[ind++] = alternate[itr.second];
alternate[itr.second] = now;
now++;
}
}
return l;
}
//----------------------
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
int ind = -1;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n) ind = i;
}
vector<int> alternate(n);
long long crp = 1;
if(ind == -1){
for(int i = 0; i < n; i++){
alternate[i] = i+1;
}
for(int i = 1; i <= n; i++){
crp = (crp * i)%mod;
}
}
else{
for(int i = ind; i < n; i++){
alternate[i] = inputSeq[ind] + (i - ind);
if(alternate[i] > n) alternate[i] -= n;
}
for(int i = 0; i < ind; i++){
alternate[i] = alternate[n-1] + i + 1;
if(alternate[i] > n) alternate[i] -= n;
}
}
vector<pair<int, int> > rep;
for(int i = 0; i < n; i++){
if(inputSeq[i] <= n) continue;
rep.pb({inputSeq[i], i});
}
sort(rep.begin(), rep.end());
int now = n + 1;
int x = rep.size();
long long ans = 1;
for(auto itr: rep){
int cnt = (itr.first - now);
ans = (ans * fpow((long long)(x), (long long)(cnt)))%mod;
now = itr.first + 1;
x--;
}
ans = (ans * crp)%mod;
return ans;
}
