#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000009
#define mod 998244353
using namespace std;
#include "gondola.h"
int exp(int64_t a, int x){
if(!x) return 1;
if(x&1) return a * exp(a, x-1) % modulo;
int64_t t = exp(a, x/2);
return t * t % modulo;
}
int valid(int n, int arr[]){
int x = -1;
set<int> S;
for(int i = 0; i < n; i++) S.insert(arr[i]);
if(sz(S) != n) return 0;
for(int i = 0; i < n; i++){
if(arr[i] <= n){
x = i;
break;
}
}
if(x == -1) return 1;
for(int i = 0; i < n; i++){
if(arr[(x + i) % n] <= n && arr[(x + i) % n] != (arr[x] + i - 1) % n + 1) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int arr[], int ans[]){
vector<int> A(n);
for(int i = 0; i < n; i++) A[i] = arr[i];
map<int, int> S;
for(int i = 0; i < n; i++) S[A[i]] = i;
int x = 0;
for(int i = 0; i < n; i++){
if(arr[i] <= n){
x = i;
break;
}
}
for(int i = 0; i < n; i++){
arr[(x + i) % n] = (arr[x] + i - 1) % n + 1;
}
int X = max_element(all(A)) - A.begin();
for(int i = n + 1; i <= A[X]; i++){
if(S.count(i)) ans[i - n - 1] = arr[S[i]], arr[S[i]] = i;
else ans[i - n - 1] = arr[X], arr[X] = i;
}
return A[X] - n;
}
//----------------------
int countReplacement(int n, int arr[]){
if(!valid(n, arr)) return 0;
int ans = 1;
vector<int> seq;
for(int i = 0; i < n; i++) if(arr[i] > n) seq.pb(arr[i]);
if(sz(seq) == n) ans = n;
seq.pb(n);
sort(all(seq));
for(int i = 1; i < sz(seq); i++){
ans = 1ll * ans * exp(sz(seq) - i, seq[i] - seq[i - 1] - 1) % modulo;
}
return ans;
}
