#include<bits/stdc++.h>
#include"gondola.h"
using namespace std;
long long get(int u, int v){
if(v==0) return 1;
long long k = get(u, v/2);
k%=1000000009;
k*=k;
k%=1000000009;
if(v%2==1) return k*u;
return k;
}
int valid(int n, int b[]){
int a[2*n];
map<int, int> mp;
for(int i = 0; i < n; i++){
a[i] = b[i];
a[i+n] = b[i];
if(mp[a[i]]==1) return 0;
mp[a[i]]=1;
}
for(int i = 0; i < n; i++){
if(a[i]<=n){
int k = a[i];
for(int j = i; j<2*n; j++){
if(a[j]<=n&&a[j]!=k) return 0;
k++;
if(k>n) k-=n;
}
return 1;
}
}
return 1;
}
int replacement(int n, int a1[], int b[]){
int a[2*n];
map<int, int> mp;
for(int i = 0; i < n; i++){
a[i] = a1[i];
a[i+n] = a1[i];
}
int ind = -1, l = 0;
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
if(a[i]<=n){
int k = a[i];
ind = i;
for(int j = i; j<i+n; j++){
if(a[j]!=k){
v.push_back({a[j], k});
}
k++;
if(k>n) k-=n;
}
break;
}
}
if(ind==-1) {
for(int i = 0; i < n; i++){
v.push_back({a[i], i+1});
}
}
int k = n+1;
sort(v.begin(), v.end());
for(auto i : v){
int ok = i.second;
b[l] = ok;
l++;
while(i.first>k){
b[l] = k;
l++;
k++;
}
k = i.first+1;
}
return l;
}
int countReplacement(int n, int b[]){
if(valid(n, b)==0) return 0;
long long ans = 1;
int a[2*n];
map<int, int> mp;
vector<int> v;
for(int i = 0; i < n; i++){
a[i] = b[i];
a[i+n] = b[i];
}
for(int i = 0; i < n; i++){
if(a[i]>n) v.push_back(a[i]);
}
sort(v.begin(), v.end());
int l = n;
int k = v.size();
if(v.size()==n) k = n;
for(auto i : v){
int x = i - l;
ans*=get(k, x);
k--;
ans%=1000000009;
l = i;
}
if(v[0]>n) ans*=n;
ans%=1000000009;
return ans;
}
