#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int N = 3e5;
const ll mod = 1e9+9;
int bar[N];
ll f(ll x, int y) {
ll res = 1;
while (y) {
if(y&1)res = res*x%mod;
y >>= 1, x=x*x%mod;
}
return res;
}
int valid(int n, int a[])
{
set<int> s;
rep(i, 0, n)s.insert(a[i]);
if (sz(s) != n)return 0;
int pos, san = -1;
rep(i, 0, n)
if (a[i] <= n)pos = i, san = a[i];
if (san == -1)return 1;
vector<int> sb(n+1);
int x = san+1; sb[san] = pos;
if (x > n)x -= n;
while (x != san) {
sb[x] = (pos+1)%n;
pos += 1, x += 1;
if (x > n)x -= n;
}
bool ok = true;
rep(i, 0, n) {
if (a[i]>n)continue;
ok &= sb[a[i]] == i;
}
return ok;
}
//----------------------
int replacement(int n, int a[], int ans[])
{
return -2;
}
//----------------------
int countReplacement(int n, int a[])
{
if (!valid(n, a))return 0;
int pos, san = -1;
rep(i, 1, n+1)bar[i] = 1;
int free = n;
rep(i, 0, n) {
if (a[i] <= n)pos = i, san = a[i], free -= 1;
bar[a[i]] = 1;
}
vector<P> b;
int ans = 1;
if (san == -1) {
ans = n;
rep(i, 0, n)
b.push_back({a[i], i+1});
}
else {
int x = san+1;
if (x > n)x -= n;
while (x != san) {
int np = (pos+1)%n;
if (a[np] > n)b.push_back({a[np], x});
pos += 1, x += 1;
if (x > n)x -= n;
}
}
sort(all(b));
if (b.empty())return 1;
ans = (ll)ans*(ll)f(free, b[0].first-n-1)%mod; free -= 1;
int last = b[0].first+1;
rep(i, 1, sz(b)) {
ans = (ll)ans*(ll)f(free, b[i].first-last)%mod;
last = b[i].first+1;
free -= 1;
}
return (int)ans;
}
//1 2 3 4 5 6
//6 1 2 3 4 5
//5 6 1 2 3 4
//4 5 6 1 2 3
//3 4 5 6 1 2
//2 3 4 5 6 1
//1 2 3 8 9
