#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
int valid(int n, int s[]) {
int original = -1;
map<int, int> counts;
rep(i, n) {
if (s[i] < 1) return 0;
if (counts[s[i]]) return 0;
counts[s[i]] = 1;
if (s[i] <= n) {
if (original == -1) {
original = i;
} else {
if ((i + s[original]) % n != (s[i] + original) % n) {
return 0;
}
}
}
}
return 1;
}
//----------------------
int replacement(int n, int s[], int r[])
{
vpii changed;
int offset = 0;
rep(i, n) {
if (s[i] > n) {
changed.emplace_back(s[i], i);
} else {
offset = (s[i] - i - 1 + n) % n;
}
}
sort(all(changed));
int curr = n;
forin(change, changed) {
int val = (change.second + offset) % n + 1;
while (curr < change.first) {
r[curr++ - n] = val;
val = curr;
}
}
return curr - n;
}
//----------------------
const int mod = 1000000009;
ll modpow(ll a, ll b) {
ll curr = a;
ll res = 1;
while(b) {
if (b % 2) {
res *= curr;
res %= mod;
}
curr *= curr;
curr %= mod;
b /= 2;
}
return res;
}
int countReplacement(int n, int s[])
{
if (!valid(n, s)) return 0;
ll res = 1;
vii changed;
bool original = false;
rep(i, n) {
if (s[i] > n) {
changed.emplace_back(s[i]);
} else {
original = true;
}
}
sort(all(changed));
if (!original) res = n;
int last = n;
vii diffs;
forin(change, changed) {
diffs.emplace_back(change - last - 1);
last = change;
}
reverse(all(diffs));
rep(i, diffs.size()) {
res *= modpow(i + 1, diffs[i]);
res %= mod;
}
return (int)res;
}
