#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int MAX = 2.5e5 + 5;
bitset<MAX> is;
int valid(int n, int a[]) {
int shift = -1;
for (int i = 0; i < n; i++) {
if (a[i] <= n) {
if (shift == -1) shift = (a[i] - 1 - i + n) % n;
else if ((a[i] - 1 - i + n) % n != shift) return 0;
}
if (is[a[i]]) return 0;
is[a[i]] = 1;
}
return 1;
}
int p[MAX];
int replacement(int n, int a[], int b[]) {
int mx = *max_element(a, a + n);
fill(p + 1, p + mx + 1, -1);
int shift = -1;
for (int i = 0; i < n; i++) {
p[a[i]] = i;
if (a[i] <= n && shift == -1) shift = (a[i] - 1 - i + n) % n;
}
if (shift == -1) shift = 0;
for (int i = 1; i <= n; i++) p[i] = (i - 1 - shift + n) % n;
for (int i = n + 1; i <= mx; i++) if (p[i] == -1) p[i] = p[mx];
for (int i = 1; i <= n; i++) a[p[i]] = i;
int sz = 0;
for (int i = n + 1; i <= mx; i++) b[sz++] = a[p[i]], a[p[i]] = i;
return sz;
}
const int MOD = 1e9 + 9;
inline int power(int d, int up) {
int re = 1;
while (up) {
if (up & 1) re = 1ll * re * d % MOD;
d = 1ll * d * d % MOD;
up >>= 1;
}
return re;
}
int countReplacement(int n, int a[]) {
int shift = -1;
unordered_set<int> us;
for (int i = 0; i < n; i++) {
if (us.count(a[i])) return 0;
if (a[i] <= n) {
if (shift == -1) shift = (a[i] - 1 - i + n) % n;
else if ((a[i] - 1 - i + n) % n != shift) return 0;
}
us.insert(a[i]);
}
int ans = (shift == -1 ? n : 1), cnt = 0;
sort(a, a + n);
for (int i = 0; i < n; i++) if (a[i] > n) {
if (i == 0 || a[i - 1] <= n) {
cnt = n - i;
ans = 1ll * ans * power(cnt, a[i] - n - 1) % MOD;
} else {
ans = 1ll * ans * power(cnt, a[i] - a[i - 1] - 1) % MOD;
}
cnt--;
}
return ans;
}
