#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+9;
ll binpow(ll a, ll b) {
ll r = 1;
while (b) {
if (b&1) r = (r*a)%MOD;
a = (a*a)%MOD;
b /= 2;
}
return r;
}
int valid(int n, int a[]) {
int b[n];
for (int i = 0; i < n; i++) b[i] = a[i];
for (int i = 0; i < n; i++) {
if (a[i] <= n) {
int s = (i-a[i]+1+n)%n;
for (int j = 0; j < n; j++) b[(s+j)%n] = j+1;
break;
}
}
bool ok = 1;
set<int> s;
for (int i = 0; i < n; i++) {
if (b[i] > a[i] || (b[i] < a[i] && a[i] <= n)) ok = 0;
s.insert(a[i]);
}
if (s.size() != n) ok = 0;
return ok;
}
int replacement(int n, int a[], int r[]) {
int b[n];
map<int, int> mp;
for (int i = 0; i < n; i++) {
b[i] = a[i];
if (a[i] > n) mp[a[i]] = i;
}
if (mp.size() == n) for (int i = 0; i < n; i++) b[i] = i+1;
else for (int i = 0; i < n; i++) {
if (a[i] <= n) {
int s = (i-a[i]+1+n)%n;
for (int j = 0; j < n; j++) b[(s+j)%n] = j+1;
break;
}
}
int l = 0;
if (mp.size()) for (int i = n+1; i <= mp.rbegin()->first; i++) {
if (mp.count(i)) r[l++] = b[mp[i]], b[mp[i]] = i;
else r[l++] = b[mp.rbegin()->second], b[mp.rbegin()->second] = i;
}
return l;
}
int countReplacement(int n, int a[]) {
if (!valid(n, a)) return 0;
ll ans = 1;
set<ll> s;
for (int i = 0; i < n; i++) if (a[i] > n) s.insert(a[i]);
if (s.size() == n) ans = n;
ll pr = n;
ll cnt = s.size();
for (ll x : s) {
ans = (ans*binpow(cnt, max(0ll, x-pr-1)))%MOD;
cnt--;
pr = x;
}
return ans;
}
