// In the name of Allah
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 4;
const int mod = 1e9 + 9;
map<int, int> ind; int val[maxn];
ll power(ll a, ll b) {
if (b == 0) return 1;
return power(a * a % mod, b / 2) * ((b & 1) ? a : 1) % mod;
}
int valid(int n, int a[]) {
int j = -1, mx = 0;
for (int i = 0; i < n; i++) {
a[i]--;
if (ind.find(a[i]) != ind.end()) return 0;
else ind[a[i]] = i;
if (a[i] > a[mx]) mx = i;
if (a[i] < n) {
int k = (i - a[i] + n) % n;
if (j == -1 || j == k) j = k;
else return 0;
}
}
return 1;
}
int replacement(int n, int a[], int res[]) {
int j = -1, mx = 0;
for (int i = 0; i < n; i++) {
a[i]--;
if (ind.find(a[i]) != ind.end()) return 0;
else ind[a[i]] = i;
if (a[i] > a[mx]) mx = i;
if (a[i] < n) {
int k = (i - a[i] + n) % n;
if (j == -1 || j == k) j = k;
else return 0;
}
}
if (j == -1) j = 0;
for (int i = j; i < j + n; i++) val[i % n] = i - j;
for (int i = n; i <= a[mx]; i++) {
if (ind.find(i) != ind.end()) {
int j = ind[i];
res[i - n] = val[j] + 1;
val[j] = i;
}
else {
int j = ind[a[mx]];
res[i - n] = val[j] + 1;
val[j] = i;
}
}
return (a[mx] + 1) - n;
}
int countReplacement(int n, int a[]) {
int j = -1, mx = 0;
for (int i = 0; i < n; i++) {
a[i]--;
if (ind.find(a[i]) != ind.end()) return 0;
else ind[a[i]] = i;
if (a[i] > a[mx]) mx = i;
if (a[i] < n) {
int k = (i - a[i] + n) % n;
if (j == -1 || j == k) j = k;
else return 0;
}
}
ll ans = 1, R = 0;
for (int i = 0; i < n; i++) {
if (ind.find(i) == ind.end()) R++;
}
sort(a, a + n); int lst = n;
for (int i = 0; i < n; i++) {
if (a[i] < lst) continue;
ans *= power(R, a[i] - lst); ans %= mod;
lst = a[i] + 1; R--;
}
if (j == -1) {
ans *= n; ans %= mod;
}
return ans;
}
