#include "gondola.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;
using ll = long long;
int valid(int n, int inputSeq[])
{
set<int> seen;
for (int i(0); i < n; ++i)
{
if (seen.count(inputSeq[i]))
return 0;
seen.insert(inputSeq[i]);
}
for (int i(0); i < n; ++i)
if (inputSeq[i] <= n)
{
for (int j(1); j < n; ++j)
if (inputSeq[(i+j)%n] <= n and inputSeq[(i+j)%n]%n != (inputSeq[i] + j)%n)
return 0;
return 1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
assert(valid(n, gondolaSeq));
int posNormal(0);
while (posNormal < n and gondolaSeq[posNormal] > n)
posNormal++;
if (posNormal != n)
rotate(gondolaSeq, gondolaSeq + (posNormal - gondolaSeq[posNormal]+1+n)%n, gondolaSeq + n);
vector<pair<int, int>> toReplace;
for (int i(0); i < n; ++i)
if (gondolaSeq[i] > n)
toReplace.emplace_back(gondolaSeq[i]-n, i+1);
sort(toReplace.begin(), toReplace.end());
int curLen(0);
for (auto [val, id] : toReplace)
while (curLen < val)
{
replacementSeq[curLen++] = id;
id = curLen+n;
}
return curLen;
}
//----------------------
template<const int32_t MOD>
struct ModInt {
long long x;
ModInt() : x(0) {}
ModInt(long long u) : x(u) { x %= MOD; if (x < 0) x += MOD;}
friend bool operator == (const ModInt& a, const ModInt& b) { return a.x == b.x; }
friend bool operator != (const ModInt& a, const ModInt& b) { return a.x != b.x; }
friend bool operator < (const ModInt& a, const ModInt& b) { return a.x < b.x; }
friend bool operator > (const ModInt& a, const ModInt& b) { return a.x > b.x; }
friend bool operator <= (const ModInt& a, const ModInt& b) { return a.x <= b.x; }
friend bool operator >= (const ModInt &a, const ModInt& b) { return a.x >= b.x; }
static ModInt sign(long long k) { return ((k & 1) ? ModInt(MOD-1) : ModInt(1)); }
ModInt& operator += (const ModInt& m) { x += m.x; if(x >= MOD) x -= MOD; return *this; }
ModInt& operator -= (const ModInt& m) { x -= m.x; if(x < 0LL) x += MOD; return *this; }
ModInt& operator *= (const ModInt& m) { x = (1LL * x * m.x) % MOD; return *this; }
friend ModInt operator - (const ModInt& a) { ModInt res(a); if(res.x) res.x = MOD - res.x; return res; }
friend ModInt operator + (const ModInt& a, const ModInt& b) { return ModInt(a) += ModInt(b); }
friend ModInt operator - (const ModInt& a, const ModInt& b) { return ModInt(a) -= ModInt(b); }
friend ModInt operator * (const ModInt& a, const ModInt& b) { return ModInt(a) *= ModInt(b); }
static long long fp(long long u, long long k) {
long long res = 1LL;
while(k > 0LL) {
if(k & 1LL) res = (res * u) % MOD;
u = (u * u) % MOD;
k /= 2LL;
}
return res;
}
static constexpr int mod() {return MOD;}
ModInt fastpow(long long k) { return ModInt(fp(x, k)); }
ModInt inv() { return ModInt(fp(x, MOD-2)); }
ModInt& operator /= (const ModInt& m) { return *this *= ModInt(m).inv(); }
friend ModInt operator / (const ModInt& a, const ModInt& b) { return ModInt(a) *= ModInt(b).inv(); }
friend ostream& operator << (ostream& out, const ModInt& a) { return out << a.x; }
friend istream& operator >> (istream& in, ModInt& a) {return in >> a.x;}
};
const int MOD = 1e9 + 9;
using Mint = ModInt<MOD>;
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq))
return 0;
int posValid(0);
while (posValid < n and inputSeq[posValid] > n)
posValid++;
Mint sol(1);
vector<int> toReplace;
for (int i(0); i < n; ++i)
if (inputSeq[i] > n)
toReplace.push_back(inputSeq[i] - n);
sort(toReplace.begin(), toReplace.end());
int prv(0);
for (int i(0); i < (int)toReplace.size(); ++i)
{
sol *= Mint(toReplace.size() - i).fastpow(toReplace[i] - prv-1);
prv = toReplace[i];
}
if (posValid == n)
sol *= n;
return sol.x;
}
