#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
#include "gondola.h"
int valid(int n, int inputSeq[]) {
int ind = -1, x = -1;
for(int i = 0; i < n; i++) {
if(inputSeq[i] <= n) {
ind = i;
x = inputSeq[i];
break;
}
}
for(int i = ind + 1; i < n; i++) {
if(inputSeq[i] <= n and (x + i - ind - 1) % n + 1 != inputSeq[i])
return 0;
}
set < int > s;
for(int i = 0; i < n; i++)
s.insert(inputSeq[i]);
return s.size() == n;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int ind = 1;
for(int i = 0; i < n; i++) {
if(gondolaSeq[i] <= n) {
ind = (gondolaSeq[i] - 1 - i + n) % n + 1;
break;
}
}
vector < ii > v;
for(int i = 0; i < n; i++) {
v.push_back(ii(gondolaSeq[i], (ind + i - 1) % n + 1));
}
sort(v.begin(), v.end());
int nxt = n + 1, sz = 0;
foreach(it, v) {
int x = it -> first;
int i = it -> second;
while(nxt <= x) {
replacementSeq[sz++] = i;
i = nxt;
nxt++;
}
}
return sz;
}
//----------------------
const int mod = 1e9 + 9;
int power(int x, int k) {
int res = 1;
while(k) {
if(k & 1)
res = (ll) res * x % mod;
x = (ll) x * x % mod;
k >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq))
return 0;
int ans = 1;
int mx = *max_element(inputSeq, inputSeq + n);
set < int > s;
for(int i = 0; i < n; i++)
if(inputSeq[i] > n)
s.insert(inputSeq[i]);
int bef = n, cnt = 0;
foreach(it, s) {
int x = *it;
ans = (ll) ans * power(s.size() - cnt, x - bef - 1) % mod;
bef = x;
cnt++;
}
if(*min_element(inputSeq, inputSeq + n) > n)
ans = (ll) ans * n % mod;
return ans;
}
