#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int A[])
{
set<int> seen;
int six = -1;
for (int i = 0; i < n; ++i) {
if (seen.count(A[i])) return 0;
seen.insert(A[i]);
if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
}
if (six == -1) return 1;
for (int i = 0; i < n; ++i) {
int j = (six+i)%n;
if (A[j] <= n && A[j] != i+1)
return false;
}
return 1;
}
//----------------------
int replacement(int n, int A[], int ret[])
{
int six = 0;
for (int i = 0; i < n; ++i) {
if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
}
map<int, int> num;
for (int i = 0; i < n; ++i) {
int j = (six+i)%n;
if (A[j] > n)
num[A[j]] = i+1;
}
int cnt = 0, v = n;
for (auto p : num) {
int x = p.second, y = p.first;
while (x < y) {
ret[cnt++] = x;
x = ++v;
}
}
return cnt;
}
//----------------------
const int MOD = 1e9+9;
static inline int mul(int a, int b) { return (a*1ll*b)%MOD; }
static inline int modpow(int a, int b) {
int ans = 1;
while (b) {
if (b&1) ans = mul(ans, a);
a = mul(a, a);
b >>= 1;
}
return ans;
}
int countReplacement(int n, int A[])
{
if (!valid(n, A)) return 0;
int six = -1;
vector<int> big;
for (int i = 0; i < n; ++i) {
if (A[i] <= n) six = (i-(A[i]-1)+n)%n;
else big.push_back(A[i]);
}
sort(big.begin(), big.end(), greater<int>());
int ans = six == -1 ? n : 1;
int prev = n;
while (!big.empty()) {
int x = big.back();
big.pop_back();
ans = mul(ans, modpow(big.size()+1, x-prev-1));
prev = x;
}
return ans;
}
