#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef pair<int, int> ip;
typedef long long ll;
int valid(int n, int inputSeq[])
{
map<ll,bool> cek;
int now = -1;
for (int i = 0; i < n; i++) {
if (cek[inputSeq[i]]) return 0;
cek[inputSeq[i]] = true;
if (inputSeq[i] <= n) {
if (now == -1) now = inputSeq[i];
else if (now != inputSeq[i]) return 0;
}
if (now != -1) now = (now%n)+1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int arr[100010];
for (int i = 0; i <= n; i++) {
if (i == n) {
for (int j = 0; j < n; j++) {
arr[j] = j+1;
}
break;
}
if (gondolaSeq[i] <= n) {
for (int j = 0; j < n; j++) {
arr[j] = (gondolaSeq[i]+(j-i)+n)%n;
if (arr[j] == 0) arr[j] = n;
}
break;
}
}
vector <ip> v;
v.clear();
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] != arr[i]) {
v.pb(mp(gondolaSeq[i], i));
}
}
sort(v.begin(), v.end());
int idx = 0;
int maks;
if (v.size() > 0) {
maks = v[v.size()-1].fi;
} else {
return 0;
}
for (int x = n+1; x <= maks; x++) {
int tmp = v[idx].se;
replacementSeq[x-(n+1)] = arr[tmp];
// cout << x << " " << tmp << " " << arr[tmp] << "\n";
arr[tmp] = x;
if (v[idx].fi == x) {
idx++;
}
}
return maks-n;
}
//----------------------
const ll MOD = 1e9+9;
ll pwr(ll x, ll p) {
if (x == 0) return 0;
if (x == 1) return 1;
if (p == 1) return x;
ll a = pwr((x*x)%MOD, p/2);
if (p%2 == 1) return (a*x)%MOD;
return a;
}
int countReplacement(int N, int Seq[])
{
if (valid(N, Seq) == 0) {
return 0;
}
ll n = N, inputSeq[100010];
for (int i = 0; i < N; i++) inputSeq[i] = Seq[i];
ll arr[100010];
bool aman = false;
for (ll i = 0; i <= n; i++) {
if (i == n) {
for (ll j = 0; j < n; j++) {
arr[j] = j+1;
}
aman = true;
break;
}
if (inputSeq[i] <= n) {
for (ll j = 0; j < n; j++) {
arr[j] = (inputSeq[i]+(j-i)+n)%n;
if (arr[j] == 0) arr[j] = n;
}
break;
}
}
vector <ll> v;
v.pb(n);
for (ll i = 0; i < n; i++) {
if (inputSeq[i] > n) v.pb(inputSeq[i]);
}
sort(v.begin(), v.end());
ll ct = 1, tot = v.size();
// cout << tot << " tot\n";
for (ll i = 1; i < tot; i++) {
// cout << i << ". " << v[i] << "\n";
ll tmp = v[i]-v[i-1]-1ll;
if (tmp == 0) continue;
ct = (ct * pwr(tot-i, tmp))%MOD;
// cout << i << " " << ct << " aaaa\n";
}
if (aman) ct = (ct*n)%MOD;
return ct;
}
// BAWAH ADALAH GRADER ----------------------------------------------------------
//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;
//}
