#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "gondola.h"
#endif
const int mod = 1000000009;
int P(int a, int b) {
if(b == 0) return 1;
if(b & 1) return 1ll * P(a, b - 1) * a % mod;
int c = P(a, b / 2);
return 1ll * c * c % mod;
}
void G(int a[], int b[], int n) {
for(int i = 0; i < n; ++i) a[i] = b[i];
}
void D(int a[], int n) {
int j = 0;
for(int i = 0; i < n; ++i) {
if(a[i] <= n) {
j = i - a[i] + 1;
if(j < 0) j += n;
break;
}
}
int b[n];
G(b, a, n);
for(int i = j; i < n; ++i) {
a[i - j] = b[i];
}
for(int i = 0; i < j; ++i) {
a[n - j + i] = b[i];
}
}
int valid(int n, int _g[]) {
int g[n];
G(g, _g, n);
D(g, n);
int d[n];
G(d, g, n);
sort(d, d + n);
for(int i = 1; i < n; ++i) {
if(d[i] == d[i - 1]) return 0;
}
for(int i = 0; i < n; ++i) {
if(g[i] <= n && g[i] != i + 1) return 0;
}
return 1;
}
int replacement(int n, int _g[], int r[]) {
int g[n];
G(g, _g, n);
D(g, n);
vector<pair<int, int> > v;
for(int i = 0; i < n; ++i) {
if(g[i] > n) {
v.push_back({g[i], i});
}
}
sort(v.begin(), v.end());
int x = n + 1, rg = 0;
for(int i = 0; i < (int)v.size(); ++i) {
int gf = v[i].second + 1;
while(x <= v[i].first) {
r[rg] = gf;
gf = x;
++x;
++rg;
}
}
return rg;
}
int countReplacement(int n, int _g[]) {
int g[n];
G(g, _g, n);
if(!valid(n, g)) return 0;
vector<int> v = {n};
sort(g, g + n);
for(int i = 0; i < n; ++i) {
if(g[i] > n) {
v.push_back(g[i]);
}
}
int dr = (g[0] > n ? n : 1);
for(int i = 1; i < (int)v.size(); ++i) {
dr = 1ll * dr * P((int)v.size() - i, v[i] - v[i - 1] - 1) % mod;
}
return dr;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
return 0;
}
#endif
