#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;
int valid(int n, int inputSeq[]) {
int pos = -1;
set<ll> b;
for(int i = 0; i < n; i++)
b.insert(inputSeq[i]);
if(b.size() != n)return 0;
for(int i = 0; i < n; i++) {
if(inputSeq[i] <= n) {
pos = i;
break;
}
}
if(pos == -1)return 1;
ll a = inputSeq[pos];
ll nxt = pos;
for(int j = 0; j <= n; j++) {
if(inputSeq[nxt] <= n && inputSeq[nxt] != a)return 0;
a++;
if(a == n + 1)a = 1;
nxt = (nxt + 1) % n;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector<pair<int, int>> z;
int pos = -1;
int a[n] = {0};
for(int i = 0; i < n; i++) {
if(gondolaSeq[i] <= n) {
pos = i;
}
z.pb(mp(gondolaSeq[i], i));
}
int b = (pos == -1 ? 1 : gondolaSeq[pos]);
pos = (pos == -1 ? 0 : pos);
for(int j = 0 ; j < n; j++) {
a[pos] = b;
pos = (pos + 1) % n;
b++;
if(b == n + 1)b = 1;
}
int cur = 0;
ll mx = n;
sort(z.begin(), z.end());
for(auto u : z) {
if(u.f <= n)continue;
replacementSeq[cur++] = a[u.s];
mx++;
while(mx != u.f) {
replacementSeq[cur++] = mx;
mx++;
}
}
return cur;
}
const ll mod = 1e9 + 9;
ll bp(ll a, ll b) {
ll c = 1ll;
a %= mod;
if(b >= 1e6)assert(0);
while(b) {
if(b&1ll) {
c = c * a % mod;
}
b >>= 1ll;
a = a * a % mod;
}
return c;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq))return 0;
int cnt = 0;
vector<ll> z;
for(int i = 0; i < n; i++) {
cnt += (inputSeq[i] <= n);
if(inputSeq[i] > n)
z.pb(inputSeq[i]);
}
if(cnt == n)return 1;
ll ans = 1;
if(cnt == 0) {
sort(z.begin(), z.end());
ll mx = n + 1;
assert(z.size() <= 100);
for(ll j = 0; j < z.size(); j++) {
ll a = z[j] - mx;
assert(mx <= z[j]);
assert(ans < mod && ans >= 0);
ll x = ans;
ll y = bp((ll)(z.size() - j), a);
assert(x < mod && x >= 0);
assert(y < mod && y >= 0);
ans = x * y % mod;
assert(ans < mod && ans >= 0);
mx = z[j] + 1;
}
for(ll j = 1; j <= n; j++) {
assert(ans < mod && ans >= 0);
ans = (((long long)ans % mod) * ((long long)j % mod)) % mod;
assert(ans < mod && ans >= 0);
}
} else {
sort(z.begin(), z.end());
ll mx = n + 1;
for(int j = 0; j < z.size(); j++) {
ll a = z[j] - mx;
ans = ans * bp((ll)(z.size() - j), a) % mod;
mx = z[j] + 1;
}
}
return ans;
}
/*
int gondolaSequence[100001];
int replacementSequence[250001];
int main()
{
int i, n, tag;
int nr;
assert(scanf("%d", &tag)==1);
assert(scanf("%d", &n)==1);
for(i=0;i< n;i++)
assert( scanf("%d", &gondolaSequence[i]) ==1);
switch (tag){
case 1: case 2: case 3:
printf("%d\n", valid(n, gondolaSequence));
break;
case 4: case 5: case 6:
nr = replacement(n, gondolaSequence, replacementSequence);
printf("%d ", nr);
if (nr > 0)
{
for (i=0; i<nr-1; i++)
printf("%d ", replacementSequence[i]);
printf("%d\n", replacementSequence[nr-1]);
}
else printf("\n");
break;
case 7: case 8: case 9: case 10:
printf("%d\n", countReplacement(n, gondolaSequence));
break;
}
return 0;
}
/**/
