#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
using ll = long long;
int valid(int n, int a[])
{
bool y = true;
for (int i = 1; y && i < n; ++i) y = (a[i] - a[i - 1] + n) % n == 1;
return y;
}
//----------------------
int replacement(int n, int a[], int ans[])
{
int org = -1;
for (int i = 0; i < n; ++i)
if (a[i] <= n)
{
int norg = (i - a[i] + 1 + n) % n;
assert (org == -1 || org == norg);
org = norg;
}
if (org == -1) org = 0;
vector < pair < int, int > > v;
for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back ({ a[i], (i - org + n) % n + 1 });
sort (v.begin (), v.end ());
int i = 0;
for (auto &x : v)
{
while (x.first != x.second)
{
ans[i] = x.second;
x.second = i + n + 1;
++i;
}
}
return i;
}
//----------------------
ll MOD = 1000000009;
ll
binpow (ll a, ll b)
{
ll ans = 1;
while (b)
{
if (b % 2) (ans *= a) %= MOD;
b /= 2;
if (b) (a *= a) %= MOD;
}
return ans;
}
int countReplacement(int n, int a[])
{
int org = -1;
for (int i = 0; i < n; ++i)
if (a[i] <= n)
{
int norg = (i - a[i] + 1 + n) % n;
if (org != -1 && org != norg) return 0;
org = norg;
}
bool ind = false;
if (org == -1) org = 0, ind = true;
vector < ll > v;
for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back (a[i]);
sort (v.begin (), v.end ());
ll vs = v.size (), ans = 1, p = n;
for (auto &x : v)
(ans *= binpow (vs--, x - p - 1)) %= MOD, p = x;
if (ind) (ans *= (ll) n) %= MOD;
return ans;
}
