#include "gondola.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
int valid(int n, int is[])
{
set<int> s;
int x=-1;
for(int i=0;i<n;i++){
if(is[i]<=n){
x=i;
}
if(s.find(is[i])!=s.end()){
return 0;
}
s.insert(is[i]);
}
if(x==-1){
return 1;
}
for(int i=x,cnt=0;cnt<n;i=(i+1)%n,cnt++){
if(is[i]<=n && (is[i]-is[x]+n)%n!=(i-x+n)%n){
return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int x=-1;
for(int i=0;i<n;i++){
if(gondolaSeq[i]<=n){
x=i;
}
}
vector<pair<int,int> > g;
if(x==-1){
x=0;
for(int i=0;i<n;i++){
g.push_back({gondolaSeq[i],i+1});
}
}
else{
for(int i=x,cnt=0,z=gondolaSeq[x];cnt<n;i=(i+1)%n,cnt++,z=(z+1)%n+(n*(z==n-1))){
if(gondolaSeq[i]>n){
g.push_back({gondolaSeq[i],z});
}
}
}
sort(g.begin(),g.end());
int nw=n+1,f=0;
for(auto y:g){
replacementSeq[f]=y.sc;
f++;
nw++;
for(;nw<=y.fs;f++,nw++){
replacementSeq[f]=nw-1;
}
}
return f;
}
//----------------------
const int mod=1e9+9;
int mul(int x,int y){
return 1ll*x*y%mod;
}
int po(int x,int y){
int z=1;
while(y){
if(y&1){
z=mul(z,x);
}
x=mul(x,x);
y>>=1;
}
return z;
}
int countReplacement(int n, int is[])
{
if(!valid(n,is)){
return 0;
}
int x=-1;
for(int i=0;i<n;i++){
if(is[i]<=n){
x=i;
}
}
vector<pair<int,int> > g;
int ans=1;
if(x==-1){
x=0;
for(int i=0;i<n;i++){
g.push_back({is[i],i+1});
}
ans=n;
}
else{
for(int i=x,cnt=0,z=is[x];cnt<n;i=(i+1)%n,cnt++,z=(z+1)%n+(n*(z==n-1))){
if(is[i]>n){
g.push_back({is[i],z});
}
}
}
sort(g.begin(),g.end());
int p=n,q=g.size();
for(auto h:g){
ans=mul(ans,po(q,h.fs-p-1));
p=h.fs;
q--;
}
return ans;
}
