#include "gondola.h"
#include <bits/stdc++.h>
#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;
template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 9;
int valid(int n, int inputSeq[])
{
vi vec(inputSeq, inputSeq + n);
sort(all(vec));
for0(i, n - 1)
{
if (vec[i] == vec[i + 1])
{
return 0;
}
}
int d = -1;
for0(i, n)
{
if (inputSeq[i] >= 1 && inputSeq[i] <= n)
{
int cur = ((inputSeq[i] - i) % n + n) % n;
if (d != -1 && d != cur)
{
return 0;
}
d = cur;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for0(i, n)
{
if (gondolaSeq[i] >= 1 && gondolaSeq[i] <= n)
{
int cur = i;
int need = gondolaSeq[i] - 1;
if (need < cur)
{
rotate(gondolaSeq, gondolaSeq + cur - need, gondolaSeq + n);
}
else if (need > cur)
{
rotate(gondolaSeq, gondolaSeq + n - (need - cur), gondolaSeq + n);
}
break;
}
}
vi pos((int)2e5 + 1, -1);
for0(i, n)
{
pos[gondolaSeq[i]] = i;
}
int mx = *max_element(gondolaSeq, gondolaSeq + n);
vi a(n);
iota(all(a), 1);
int id = 0;
int ansPos = 0;
auto addAns = [&](int x)
{
replacementSeq[ansPos++] = x;
};
fore(i, n + 1, mx)
{
if (pos[i] != -1)
{
addAns(a[pos[i]]);
a[pos[i]] = i;
}
else
{
while (id < n && a[id] == gondolaSeq[id])
{
id++;
}
addAns(a[id]);
a[id] = i;
}
}
return ansPos;
}
long long power(long long a, long long b)
{
long long r = 1;
while (b)
{
if (b & 1)
{
r = r * a % mod;
}
b /= 2;
a = a * a % mod;
}
return r;
}
int countReplacement(int n, int inputSeq[])
{
vi vec(inputSeq, inputSeq + n);
sort(all(vec));
for0(i, n - 1)
{
if (vec[i] == vec[i + 1])
{
return 0;
}
}
int d = -1;
for0(i, n)
{
if (inputSeq[i] >= 1 && inputSeq[i] <= n)
{
int cur = ((inputSeq[i] - i) % n + n) % n;
if (d != -1 && d != cur)
{
return 0;
}
d = cur;
}
}
for0(i, n)
{
if (inputSeq[i] >= 1 && inputSeq[i] <= n)
{
int cur = i;
int need = inputSeq[i] - 1;
if (need < cur)
{
rotate(inputSeq, inputSeq + cur - need, inputSeq + n);
}
else if (need > cur)
{
rotate(inputSeq, inputSeq + n - (need - cur), inputSeq + n);
}
break;
}
}
vi a;
for0(i, n)
{
if (inputSeq[i] > n)
{
a.pb(inputSeq[i]);
}
}
sort(all(a));
int cnt = 0;
for0(i, n)
{
cnt += (i + 1 != inputSeq[i]);
}
int ans = 1, last = n;
for (auto &x: a)
{
ans = (ll)ans * power(cnt, x - last - 1) % mod;
cnt--;
}
if (d == -1)
{
ans = (ll)ans * n % mod;
}
return ans;
}
