// 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 = 1e6 + 4;
const int mod = 1e9 + 9;
int ind[maxn], val[maxn];
int valid(int n, int a[]) {
int j = -1, mx = 0;
fill(ind, ind + maxn, -1);
for (int i = 0; i < n; i++) {
a[i]--;
if (ind[a[i]] != -1) 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;
fill(ind, ind + maxn, -1);
for (int i = 0; i < n; i++) {
a[i]--;
if (ind[a[i]] != -1) 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[i] != -1) {
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;
fill(ind, ind + maxn, -1);
for (int i = 0; i < n; i++) {
a[i]--;
if (ind[a[i]] != -1) 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[i] == -1) R++;
}
for (int i = n; i <= a[mx]; i++) {
if (ind[i] == -1) {
ans *= R; ans %= mod;
}
else R--;
}
return ans;
}
