#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int MOD = 1000000009;
long long multiply(long long a, long long b)
{
long long ans = ((a % MOD) * (b%MOD)) % MOD;
return ans;
}
long long exponentiate(long long a, long long b)
{
long long ans = a;
for (int i = 0; i < (b-1); i++)
{
ans = multiply(ans,b);
}
return ans;
}
int valid(int n, int inputSeq[])
{
unordered_set<int> used;
int current = -1;
for (int i = 0; i < n; i++)
{
if (current==-1 && inputSeq[i] <= n)
{
current = inputSeq[i];
continue;
}
if (inputSeq[i] > n)
{
if (used.find(inputSeq[i])!=used.end())
{
return 0;
}
used.insert(inputSeq[i]);
if (current!=-1){current++;}
}
if (inputSeq[i] <= n)
{
if (current==n && inputSeq[i] != 1)
{
return 0;
}
if (current!=n&&inputSeq[i] != current+1)
{
return 0;
}
current = inputSeq[i];
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
return 0;
}
int countReplacement(int n, int inputSeq[])
{
if (valid(n,inputSeq)==0)
{
return 0;
}
long long p = 1;
int next = n+1;
vector<int> replaced;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] > n)
{
replaced.push_back(inputSeq[i]);
}
}
sort(replaced.begin(),replaced.end());
if (replaced.size()==n)
{
p = multiply(p,n);
}
if (!replaced.empty()){
for (int i = 0; i < replaced.size()-1; i++)
{
if (next != replaced[i])
{
long long num_options = replaced.size()-i;
long long gap = replaced[i]-next;
p = multiply(p,(exponentiate(num_options,gap)));
}
next = replaced[i]+1;
}}
return p;
}
