#include "gondola.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, M = 1e9 + 9;
int valid(int n, int a[]) {
int he = -1;
set<int> s;
for(int i = 0; i < n; i++) {
if(s.count(a[i]))
return 0;
s.insert(a[i]);
}
for(int i = 0; i < n; i++) if(a[i] <= n) {
int be = (i - a[i] + n) % n;
if(he != -1 && he != be)
return 0;
he = be;
}
return 1;
}
int replacement(int n, int a[], int b[]) {
assert(valid(n, a));
int sz = 0, mx = 0;
map<int, int> mp;
int pos = -1;
for(int i = 0; i < n; i++) {
mx = max(mx, a[i]);
if(a[i] >= n) {
mp[a[i]] = i;
} else {
pos = i;
}
}
if(pos == -1) {
for(int i = 0; i < n; i++)
a[i] = i + 1;
} else {
for(int i = pos + 1; i < n; i++) {
a[i] = (a[pos] + i - pos + n - 1) % n + 1;
}
for(int i = 0; i < pos; i++) {
a[i] = (a[pos] + i - pos + n - 1) % n + 1;
}
}
for(int i = n + 1; i <= mx; i++) {
if(mp.count(i)) {
b[sz++] = a[mp[i]];
a[mp[i]] = i;
} else {
b[sz++] = a[mp[mx]];
a[mp[mx]] = i;
}
}
return sz;
}
int countReplacement(int n, int a[]) {
if(!valid(n, a)) return 0;
int mx = 0;
set<int> s;
for(int i = 0; i < n; i++) {
mx = max(mx, a[i]);
if(a[i] >= n) {
s.insert(a[i]);
}
}
int ans = 1, cnt = 0;
for(int i = mx; i >= n + 1; i--) {
if(s.count(i)) {
cnt++;
} else {
ans = 1LL * ans * cnt % M;
}
}
return ans;
}
