#include <bits/stdc++.h>
#include "gondola.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define pii pair<int, int>
#define sz(x) (int)x.size()
const int md = (int)1e9 + 9;
int pw(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = (ll)res * x % md;
y >>= 1;
x = (ll)x * x % md;
}
return res;
}
int valid(int n, int a[]) {
set<int> s(a, a + n);
if (sz(s) != n) return 0;
for (int i = 0; i < n; i++)
a[i]--;
int x = -1, y = -1;
for (int i = 0; i < n; i++) {
if (a[i] < n) {
x = i; y = a[i];
}
}
if (!~x) return 1;
int z = 0;
while (z++ < n) {
if (a[x] < n && a[x] != y) return 0;
y = (y + 1) % n; x = (x + 1) % n;
}
return 1;
}
int replacement(int n, int a[], int b[]) {
for (int i = 0; i < n; i++)
a[i]--;
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (a[i] < n) {
x = i; y = a[i];
}
}
int z = 0;
vector<pii> v = {{n - 1, -1}};
while (z++ < n) {
if (n <= a[x]) v.push_back({a[x], y});
y = (y + 1) % n; x = (x + 1) % n;
}
sort(v.begin(), v.end());
x = 0;
for (int i = 1; i < (int)v.size(); i++) {
b[x++] = v[i].ss;
for (int j = v[i - 1].ff + 1; j < v[i].ff; j++)
b[x++] = j;
}
for (int i = 0; i < x; i++)
b[i]++;
return x;
}
int countReplacement(int n, int a[]) {
set<int> s(a, a + n);
if (sz(s) != n) return 0;
for (int i = 0; i < n; i++)
a[i]--;
int x = -1, y = -1;
for (int i = 0; i < n; i++) {
if (a[i] < n) {
x = i; y = a[i];
}
}
int ans = 1;
if (!~x) {
x = 0;
ans = n;
}
int z = 0;
vector<pii> v = {{n - 1, -1}};
while (z++ < n) {
if (n <= a[x]) v.push_back({a[x], y});
y = (y + 1) % n; x = (x + 1) % n;
}
sort(v.begin(), v.end());
for (int i = 1; i < sz(v); i++)
ans = (ll)ans * pw(sz(v) - i, v[i].ff - v[i - 1].ff - 1) % md;
return ans;
}
