#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include "gondola.h"
using namespace std;
int valid(int n, int seq[]){
map<int,int> mp;
for (int i=0;i<n;i++){
if (mp.find(seq[i]) != mp.end())
return 0;
mp[seq[i]];
}
vector<int> vc(n + 1);
for (int i=0;i<=n;i++){
if (i == n)
return 1;
if (seq[i] <= n){
for (int j=i;j<i + n;j++)
vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
break;
}
}
for (int i=1;i<=n;i++)
if (vc[i] <= n and vc[i] != i)
return 0;
return 1;
}
int replacement(int n, int seq[], int ans[]){
vector<int> vc(n + 1);
vector<pair<int,int>> vc2;
for (int i=0;i<=n;i++){
if (i == n){
for (int j=0;j<n;j++)
vc[j+1] = seq[j];
}
else if (seq[i] <= n){
for (int j=i;j<i + n;j++)
vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
break;
}
}
for (int i=1;i<=n;i++){
if (vc[i] > n)
vc2.push_back({vc[i], i});
}
sort(begin(vc2), end(vc2));
int cur = n + 1, sz = 0;
for (auto [vl, id] : vc2){
// cout<<cur<<" "<<vl<<" "<<id<<endl;
while (cur < vl)
ans[sz++] = id, id = cur++;
ans[sz++] = id;
cur++;
}
return sz;
}
int mod = 1e9 + 9;
int power(int a, int b){
if (b == 0)
return 1;
int ans = power(a, b / 2);
ans = 1LL * ans * ans % mod;
if (b % 2)
ans = 1LL * ans * a % mod;
return ans;
}
int countReplacement(int n, int seq[]){
if (valid(n, seq) == 0)
return 0;
vector<int> vc(n + 1);
vector<pair<int,int>> vc2;
for (int i=0;i<=n;i++){
if (i == n){
for (int j=0;j<n;j++)
vc[j+1] = seq[j];
}
else if (seq[i] <= n){
for (int j=i;j<i + n;j++)
vc[(j - i + seq[i] - 1) % n + 1] = seq[j % n];
break;
}
}
for (int i=1;i<=n;i++){
if (vc[i] > n)
vc2.push_back({vc[i], i});
}
sort(begin(vc2), end(vc2));
int lst = n, Ways = 1 + (n - 1) * (vc2.size() == n);
for (int i=0;i<vc2.size();i++){
auto [vl, id] = vc2[i];
int k = vl - lst;
Ways = 1LL * Ways * power(vc2.size() - i, k - 1) % mod;
lst = vl;
}
return Ways;
}
