#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;
if(b > mod)assert(0);
while(b) {
if(b&1ll) {
c = c * a % mod;
}
b >>= 1ll;
a = a * a % mod;
}
return c;
}
set<vector<int>> ans;
vector<int> seq;
void rec(vector<int> cur, vector<int> need, int mx) {
bool kek = 1;
for(int j = 0; j < cur.size(); j++) {
if(cur[j] != need[j]) {
kek = 0;
}
}
if(kek) {
ans.insert(seq);
return;
}
for(int j = 0; j < need.size(); j++) {
if(mx == need[j]) {
seq.pb(cur[j]);
cur[j] = mx;
rec(cur, need, mx + 1);
cur[j] = seq.back();
seq.pop_back();
return;
}
}
for(int j = 0; j < need.size(); j++) {
if(mx < need[j]) {
seq.pb(cur[j]);
cur[j] = mx;
rec(cur, need, mx + 1);
cur[j] = seq.back();
seq.pop_back();
}
}
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq))return 0;
int cnt = 0;
int pos = -1;
vector<pair<int, int>> z;
for(int i = 0; i < n; i++) {
cnt += (inputSeq[i] <= n);
if(inputSeq[i] > n)
z.pb(mp(inputSeq[i], i));
}
if(cnt == n)return 1;
ll ans = 1;
if(cnt == 0) {
for(ll j = 1; j <= n; j++)
ans = (((long long)ans % mod) * ((long long)j % mod)) % mod;
sort(z.begin(), z.end());
ll mx = n + 1;
for(int j = 0; j < z.size(); j++) {
ll a = z[j].f - mx;
ans = ans * (bp((ll)(z.size() - j), a) % mod) % mod;
mx = z[j].f + 1;
}
} else {
sort(z.begin(), z.end());
ll mx = n + 1;
for(int j = 0; j < z.size(); j++) {
ll a = z[j].f - mx;
ans = ans * bp((ll)(z.size() - j), a) % mod;
mx = z[j].f + 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);
gondolaSequence[0] = n + 1;
srand(time(0));
for(int j = 0; j < n - 1; j++) {
gondolaSequence[j + 1] = ((abs(rand() % 5) + 1) + gondolaSequence[j]);
}
vector<int> a, b;
for(int i = 1; i <= n; i++) {
a.pb(i);
b.pb(gondolaSequence[i - 1]);
}
do {
rec(a, b, n + 1);
} while(next_permutation(a.begin(), a.end()));
cout << "kek " << ans.size() << "\n";
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;
}
/**/
