#include "gondola.h"
#include <cstdio>
#include <cassert>
#include <map>
#include <algorithm>
int valid(int n, int inputSeq[])
{
std::map<int, int> map;
for(int i=0;i<n;++i)
{
int x=inputSeq[i]-1;
if(map.find(x) != map.end()) return 0;
map.insert({x, i});
}
for(int i=0;i<n;++i)
if(map.find(i)!=map.end() && map.find((i+1)%n)!=map.end())
{
int u=map[i], v=map[(i+1)%n];
if(v != (u+1)%n)
return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i=0;i<n;++i)
if(gondolaSeq[i] <= n && gondolaSeq[i] != i+1)
{
std::rotate(gondolaSeq, gondolaSeq+(i-gondolaSeq[i]+1+n)%n, gondolaSeq+n);
}
std::map<int, int> map;
for(int i=0;i<n;++i)
{
int x=gondolaSeq[i];
assert(map.find(x) == map.end());
map.insert({x, i});
}
int l=0, v=n;
for(auto x:map)
for(int t=x.second+1;v<x.first;)
replacementSeq[l++]=t, t=++v;
return l;
}
//----------------------
using ll = long long;
const int MOD = 1e9+9;
struct mint
{
public:
int v;
mint(int _v=0): v(_v)
{
if(v < -MOD || MOD <= v) v%=MOD;
if(v<0) v+=MOD;
}
mint& operator += (const mint& o) {if((v+=o.v)>=MOD) v-=MOD; return *this;}
mint& operator -= (const mint& o) {if((v-=o.v)<0) v+=MOD;return *this;}
mint& operator *= (const mint& o) {v=(ll)v*o.v%MOD; return *this;}
friend mint operator + (mint a, const mint& b) {return a+=b;}
friend mint operator - (mint a, const mint& b) {return a-=b;}
friend mint operator * (mint a, const mint& b) {return a*=b;}
template<typename T>
friend mint pow(mint b, T p)
{
mint f(1);
for(;p;p>>=1, b*=b)
if(p&1)
f*=b;
return f;
}
};
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
std::sort(inputSeq, inputSeq+n);
mint ans(1);
if(inputSeq[0] > n)
ans *= mint(n);
int v=n;
for(int i=0;i<n;++i)
{
if(v < inputSeq[i])
ans *= pow(mint(n-i), inputSeq[i]-v-1), v=inputSeq[i];
}
return ans.v;
}
