#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
int newSeq[n + 1];
for(int i = 1; i <= n; i++) {
newSeq[i] = inputSeq[i - 1];
}
for(int i = 0; i < n; i++) {
if(inputSeq[i] >= 1 && inputSeq[i] <= n) {
newSeq[inputSeq[i]] = inputSeq[i];
int pos = i;
for(int j = inputSeq[i] + 1; j <= n; j++) {
pos++;
if(pos == n) {
pos = 0;
}
newSeq[j] = inputSeq[pos];
}
for(int j = 1; j <= inputSeq[i] - 1; j++) {
pos++;
if(pos == n) {
pos = 0;
}
newSeq[j] = inputSeq[pos];
}
break;
}
}
map<int, int> mp;
for(int i = 1; i <= n; i++) {
if(mp.count(newSeq[i])) {
return 0;
}
mp[newSeq[i]] = 1;
if(newSeq[i] >= 1 && newSeq[i] <= n && newSeq[i] != i) {
return 0;
}
}
return 1;
}
int replacement(int n, int inputSeq[], int replacementSeq[]) {
int newSeq[n + 1];
for(int i = 1; i <= n; i++) {
newSeq[i] = inputSeq[i - 1];
}
for(int i = 0; i < n; i++) {
if(inputSeq[i] >= 1 && inputSeq[i] <= n) {
newSeq[inputSeq[i]] = inputSeq[i];
int pos = i;
for(int j = inputSeq[i] + 1; j <= n; j++) {
pos++;
if(pos == n) {
pos = 0;
}
newSeq[j] = inputSeq[pos];
}
for(int j = 1; j <= inputSeq[i] - 1; j++) {
pos++;
if(pos == n) {
pos = 0;
}
newSeq[j] = inputSeq[pos];
}
break;
}
}
int maxvalue = 0, pos = 0, anspos = 0;
map<int, int> op;
for(int i = 1; i <= n; i++) {
op[newSeq[i]] = i;
maxvalue = max(maxvalue, newSeq[i]);
if(newSeq[i] == maxvalue) {
pos = i;
}
newSeq[i] = i;
}
for(int i = n + 1; i <= maxvalue; i++) {
if(op.count(i)) {
replacementSeq[anspos++] = newSeq[op[i]];
newSeq[op[i]] = i;
}
else {
replacementSeq[anspos++] = newSeq[pos];
newSeq[pos] = i;
}
}
return anspos;
}
const long long MOD = 1e9 + 9;
long long power(long long a, long long b) {
if(b == 0) {
return 1;
}
if(b == 1) {
return a;
}
long long x = power(a, b / 2);
x *= x;
x %= MOD;
if(b & 1) {
x *= a;
x %= MOD;
}
return x;
}
int countReplacement(int n, int inputSeq[]) {
long long newSeq[n + 1];
for(long long i = 1; i <= n; i++) {
newSeq[i] = inputSeq[i - 1];
}
for(long long i = 0; i < n; i++) {
if(inputSeq[i] >= 1 && inputSeq[i] <= n) {
newSeq[inputSeq[i]] = inputSeq[i];
long long pos = i;
for(long long j = inputSeq[i] + 1; j <= n; j++) {
pos++;
if(pos == n) {
pos = 0;
}
newSeq[j] = inputSeq[pos];
}
for(long long j = 1; j <= inputSeq[i] - 1; j++) {
pos++;
if(pos == n) {
pos = 0;
}
newSeq[j] = inputSeq[pos];
}
break;
}
}
map<long long, long long> mp;
long long maxx = 0, uwu = n;
for(long long i = 1; i <= n; i++) {
if(mp.count(newSeq[i])) {
return 0;
}
mp[newSeq[i]] = i;
maxx = max(maxx, newSeq[i]);
if(newSeq[i] >= 1 && newSeq[i] <= n) {
uwu--;
}
if(newSeq[i] >= 1 && newSeq[i] <= n && newSeq[i] != i) {
return 0;
}
}
long long ans = 1, prev_idx = n;
for(auto i: mp) {
if(i.first <= n) continue;
long long cur_idx = i.first;
long long cur_ans = power(uwu, (cur_idx - prev_idx - 1));
//cout << "cur_ans = " << cur_ans << "\n";
if(cur_ans != 0) {
cur_ans %= MOD;
ans *= cur_ans;
ans %= MOD;
}
uwu--;
prev_idx = cur_idx;
}
/*for(long long i = n + 1; i <= maxx; i++) {
if(mp.count(i)) {
uwu--;
}
else {
ans *= uwu;
ans %= MOD;
}
}*/
uwu = n;
for(long long i = 1; i <= n; i++) {
if(newSeq[i] >= 1 && newSeq[i] <= n) {
uwu--;
}
}
if(uwu == n) ans *= uwu;
ans %= MOD;
return ans;
}
