#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+9;
ll po(ll n, ll k)
{
if (k == 0)
return 1;
else if (k & 1)
return n * po((n * n) % mod, k / 2) % mod;
return po((n * n) % mod, k / 2);
}
int valid(int n, int sequence[])
{
vector<int> a(sequence, sequence + n);
set<int> s;
for (int i = 0; i < n; i++)
{
a[i]--;
s.insert(a[i]);
}
if (s.size() != n)
return 0;
int j = 0;
bool ok = 1;
for (int i = 0; i < n; i++)
{
if (a[i] < n)
{
ok = 0;
j = (i - a[i] + n) % n;
break;
}
}
if (ok)
return 1;
for (int k = 0; k < n; k++, j++)
{
if (a[j % n] < n && a[j % n] != k)
{
return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int sequence[], int ans[])
{
vector<int> a(sequence, sequence + n);
int j = -1;
for (int i = 0; i < n; i++)
if (a[i] <= n)
{
j = (i - (a[i] - 1) + n) % n;
break;
}
if (j == -1)
j = 1;
vector<int> initial(n);
for (int i = 0; i < n; i++)
initial[i] = (i - j + n) % n + 1;
set<pair<int, int>> change;
for (int i = 0; i < n; i++)
{
if (a[i] > n)
change.insert({a[i], i});
}
int index = 0;
int now = n;
for (auto it = change.begin(); it != change.end(); ++it)
{
int value = it->first;
int idx = it->second;
ans[index++] = initial[idx];
for (int x = now + 1; x < value; x++)
ans[index++] = x;
now = value;
}
return index;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq))
return 0;
vector<int> a(inputSeq, inputSeq + n);
vector<int> change;
int intangible = 0;
for (int i = 0; i < n; i++)
{
if (a[i] <= n)
intangible++;
else
change.push_back(a[i]);
}
if (change.empty())
return 1;
sort(change.begin(), change.end());
int ans = 1;
if (intangible == 0)
ans = (1ll * ans * n) % mod;
int now = n;
int remaining = change.size();
for (int value : change)
{
int dist = value - now - 1;
if (dist > 0)
ans = (1ll * ans * po(remaining, dist)) % mod;
now = value;
remaining--;
}
return ans;
}
