#include <bits/stdc++.h>
#include "gondola.h"
#define ll long long
#define mod 1000000009
using namespace std;
ll binpow(ll a, ll b){
ll res = 1;
while (b != 0){
if (b % 2 == 0){
b /= 2;
a *= a;
a %= mod;
}
else{
b--;
res *= a;
res %= mod;
}
}
return res;
}
int valid(int n, int inputSeq[])
{
map<int, int> ma;
int mind = -1;
for (int i = 0; i < n; i++){
if (inputSeq[i] <= n){
if (mind == -1 || inputSeq[i] < inputSeq[mind]){
mind = i;
}
}
if (ma[inputSeq[i]] > 0) return 0;
ma[inputSeq[i]]++;
}
if (mind == -1) return 1;
int va = inputSeq[mind];
for (int i = 0; i < va - 1; i++){
mind--;
if (mind < 0) mind = n - 1;
}
for (int i = 0; i < n; i++){
int no = (i + mind) % n;
if (inputSeq[no] <= n && inputSeq[no] != i + 1){
return 0;
}
}
return 1;
}
int replacement(int n, int go[], int rep[])
{
if (valid(n, go) == 0) return 0;
int mind = -1;
for (int i = 0; i < n; i++){
if (go[i] <= n){
if (mind == -1 || go[i] < go[mind]){
mind = i;
}
}
}
if (mind == -1){
mind = 0;
}
else{
int va = go[mind];
for (int i = 0; i < va - 1; i++){
mind--;
if (mind < 0) mind = n - 1;
}
}
vector<vector<int>> v;
for (int i = 0; i < n; i++){
int no = (i + mind) % n;
if (go[no] > n){
v.push_back({go[no], i + 1});
}
}
sort(v.begin(), v.end());
int ind = 0, no = n + 1, cnt = 0;
for (auto el : v){
while (el[1] != el[0]){
rep[ind] = el[1];
el[1] = no;
no++;
ind++;
}
}
return ind;
}
int countReplacement(int n, int inp[])
{
if (valid(n, inp) == 0) return 0;
int mind = -1;
for (int i = 0; i < n; i++){
if (inp[i] <= n){
if (mind == -1 || inp[i] < inp[mind]){
mind = i;
}
}
}
if (mind == -1){
mind = 0;
}
else{
int va = inp[mind];
for (int i = 0; i < va - 1; i++){
mind--;
if (mind < 0) mind = n - 1;
}
}
vector<ll> v;
for (int i = 0; i < n; i++){
int no = (i + mind) % n;
if (inp[no] > n){
v.push_back(inp[no]);
}
}
sort(v.begin(), v.end());
ll ans = 1, la = n, le = v.size();
for (auto el : v){
ll hm = el - la - 1;
ans *= binpow(le, hm);
le--;
ans %= mod;
la = el;
}
return ans;
}
