#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5+5;
int tmp[MXN];
void move(int n, int p[]) {
int mv = 0;
for(int i=0; i<n; i++)
if(p[i]<=n) {
mv = (p[i]-1-i+n)%n;
break;
}
for(int i=0; i<n; i++)
tmp[(i+mv)%n] = p[i];
for(int i=0; i<n; i++)
p[i] = tmp[i];
}
int valid(int n, int inputSeq[]) {
set<int> st;
for(int i=0; i<n; i++) st.insert(inputSeq[i]);
if(st.size()!=n) return 0;
move(n, inputSeq);
for(int i=0; i<n; i++)
if(inputSeq[i]<=n && inputSeq[i]-1!=i)
return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
move(n, gondolaSeq);
vector<int> vec;
for(int i=0; i<n; i++)
if(gondolaSeq[i]>n)
vec.push_back(i);
if(vec.empty()) return 0;
sort(vec.begin(), vec.end(), [&](int i, int j) {
return gondolaSeq[i] < gondolaSeq[j];
});
vector<int> p(n);
iota(p.begin(), p.end(), 1);
int p1=0, p2=0;
for(int i=n+1; i<=gondolaSeq[vec.back()]; i++) {
replacementSeq[p2++] = p[vec[p1]];
p[vec[p1]] = i;
if(p[vec[p1]]==gondolaSeq[vec[p1]]) p1++;
}
return p2;
}
#define SZ(x) int(x.size())
const int MOD = 1e9+9;
inline int power(int a, int b) {
int res = 1;
while(b) {
if(b&1) res = 1ll*res*a%MOD;
a = 1ll*a*a%MOD;
b >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) return 0;
vector<int> vec;
for(int i=0; i<n; i++)
if(inputSeq[i]>n)
vec.push_back(i);
sort(vec.begin(), vec.end(), [&](int i, int j) {
return inputSeq[i] < inputSeq[j];
});
int p=n+1, ans = SZ(vec)==n ? n : 1;
for(int i=0; i<SZ(vec); i++) {
ans = 1ll*ans*power(SZ(vec)-i, inputSeq[vec[i]]-p)%MOD;
p = inputSeq[vec[i]]+1;
}
return ans;
}
