#include <iostream>
#include <vector>
#include "gondola.h"
#include <limits>
#include <numeric>
#include <algorithm>
#include <map>
#define int long long
using namespace std;
int mode = 1e9+9;
signed valid(signed n, signed inputSeq[]){
int one = numeric_limits<int>::min();
map<int, bool> used;
for(int c = 0; c < n; c++){
if(inputSeq[c] <= n){
if(one == numeric_limits<int>::min()) one = c - inputSeq[c] + 1;
if((c - one + 1) % n != inputSeq[c] % n) return 0;
}
else{
if(used[inputSeq[c]]) return 0;
used[inputSeq[c]] = true;
}
}
return 1;
}
signed replacement(signed n, signed gondolaSeq[], signed replacementSeq[]){
int one = 0;
for(int c = 0; c < n; c++){
if(gondolaSeq[c] <= n) one = c - gondolaSeq[c] + 1;
}
vector<int> ind (n); iota(ind.begin(), ind.end(), 0);
auto gcomp = [&](int u, int v){return gondolaSeq[u] < gondolaSeq[v];};
sort(ind.begin(), ind.end(), gcomp);
int repg = n;
int l = 0;
vector<int> ac (n);
for(int acer = 0; acer < n; acer++){
int num = (acer - one + 1 + n) % n;
if(num == 0) num = n;
ac[acer] = num;
}
for(int rep : ind){
while(repg < gondolaSeq[rep]){
replacementSeq[l++] = ac[rep];
repg++;
ac[rep] = repg;
}
}
return l;
}
int fastpow(long long b, long long e){
long long res = 1;
for(;e != 0;e>>=1){
if(e&1) res *= b;
res %= mode;
b *= b;
b %= mode;
}
return res;
}
signed countReplacement(signed n, signed inputSeq[]){
if(!valid(n, inputSeq)) return 0;
int defs = 0;
for(int c = 0; c < n; c++) if(inputSeq[c] <= n) defs++;
vector<int> ind (n); iota(ind.begin(), ind.end(), 0);
auto gcomp = [&](int u, int v){return inputSeq[u] < inputSeq[v];};
sort(ind.begin(), ind.end(), gcomp);
int repg = n;
int p = 1;
for(int ig = 0; ig < n; ig++){
if(repg < inputSeq[ind[ig]] - 1){
p *= fastpow(n-ig,inputSeq[ind[ig]] - repg - 1);
p %= mode;
}
if(inputSeq[ind[ig]] > n) repg = inputSeq[ind[ig]];
}
if(defs == 0){
p *= n; p %= mode;
}
return p;
}
