#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
// int inputSeq[10000];
// int replacementSeq[10000];
// int gondolaSeq[10000];
int valid(int n, int inputSeq[]){
vector<pair<int,int>>v;
set<int>s;
for(int i=0; i<n; i++){
if(inputSeq[i]<=n)v.push_back({inputSeq[i],i});
if(s.find(inputSeq[i])!=s.end()){
return false;
}
s.insert(inputSeq[i]);
}
int medzineba=-1;
for(int i=0; i<n; i++){
if(inputSeq[i]<=n){
medzineba=i;
break;
}
}
if(medzineba==-1)return 1;
int k=inputSeq[medzineba];
for(int i=0; i<n; i++){
int drnachvi=(medzineba+i)%n;
if(inputSeq[drnachvi]<=n){
if(inputSeq[drnachvi]!=k)return 0;
}
k++;
if(k>n)k=1;
}
// for(int i=1; i<v.size(); i++){
// //if(v[i-1]==1)continue;
// if(v[i].first==1){
// continue;
// }
// if(v[i].first-v[i-1].first==v[i].second-v[i-1].second)continue;
// return false;
// }
//cout<<"NEKO"<<endl;
return true;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
// for(int i=0; i<n; i++){
// cout<<gondolaSeq[i]<<" ";
// }
if(valid(n,gondolaSeq)==false){
cout<<"NYAN"<<endl;
return 0;
}
else{
vector<int>v(n,0);
int m=0;
for(int i=0; i<n; i++){
if(gondolaSeq[i]<=n){
v[i]=gondolaSeq[i];
m=1;
}
}
for(int i=0; i<n; i++){
if(v[i]!=0){
for(int j=i+1; j<n; j++){
v[j]=v[j-1]+1;
v[j]%=(n+1);
if(v[j]==0)v[j]++;
}
break;
}
}
// for(int i=0; i<n; i++){
// cout<<v[i]<<" ";
// }
int l=v[n-1];
l--;
for(int i=n-2; i>=0; i--){
if(l==0)l=n;
v[i]=l;
l--;
}
// for(int i=0; i<n; i++){
// cout<<v[i]<<" ";
// }
// cout<<endl;
vector<int>bati;
//map<int,int>mp;
vector<pair<int,int>>ixvi;
for(int i=0; i<n; i++){
//mp[gondolaSeq[i]]++;
if(gondolaSeq[i]>n ){
ixvi.push_back({gondolaSeq[i]-1,v[i]});
}
}
sort(ixvi.begin(),ixvi.end());
int y=n+1;
for(int i=0; i<ixvi.size(); i++){
bati.push_back(ixvi[i].second);
for(int j=y; j<=ixvi[i].first; j++){
bati.push_back(j);
}
y=ixvi[i].first;
}
int k=0;
for(auto a:bati){
//cout<<a<<" ";
replacementSeq[k]=a;
k++;
}
return bati.size();
}
//return 0;
}
long long N=1000000009;
#define ll long long
long long batuka(ll a,ll b) {
a%=N;b%=N;
long long r=1;
while(b>0){
if(b%2==1){
//a%=N;
r=(r*a)%N;
//r%=N;
}
a=(a*a)%N;
//a%=N;
b/=2;
}
return r;
}
int countReplacement(int n, int inputSeq[]){
if(valid(n,inputSeq)==false){
return 0;
}
else{
vector<ll>v;
ll m=0;
ll j=n;
for(int i=0; i<n; i++){
if(inputSeq[i]>n){
v.push_back(inputSeq[i]);
m++;
}
}
//cout<<m<<endl;
sort(v.begin(),v.end());
long long sum=1;
if(m==n){
sum*=m;
sum%=N;
}
for(int i=0; i<v.size(); i++){
ll k=v[i]-j-1;
ll mi=m-i;
sum=(sum*batuka(mi,k))%N;
//cout<<m<<' '<<k<<endl;
sum%=N;
j=v[i];
}
return sum;
}
return 0;
}
