#include <iostream>
#include <algorithm>
#include "gondola.h"
using namespace std;
#define ll long long
ll p = 1e9+9;
ll pow(ll n1, ll n2){
if(n2==0LL){return 1LL;}
else if(n2%2==0){return pow(n1*n1%p, n2/2);}
else {return (n1 * pow(n1*n1%p, n2/2)) %p;}
}
ll b[300005];
ll cha[300005];
ll brbr[300005];
ll te[300005];
ll dingdong[4500005];
ll val;
ll fin;
ll ok;
long long ans;
bool cmp(ll x, ll y){
return b[x]<b[y];
}
int valid(int n, int a[]){
ll cn=0;
ll bruh=0;
ll sp=0;
for(ll i=0; i<n; i++){
if(a[i]<=n){cn++; sp = i;}
te[i] = a[i];
}
sort(te, te+n);
for(int i=0; i<n-1; i++){
if(te[i]==te[i+1]){bruh=1;}
}
if(bruh==1){return 0;}
if(cn>0){
for(int i=0; i<n; i++){
b[(2*n+a[sp]-sp+i-1)%n] = a[i];
}
}
else {
for(int i=0; i<n; i++){b[i] = a[i];}
}
if(cn==0){return 1;}
else {
ll bru=0;
for(int i=0; i<n; i++){
if(b[i]<=n&&b[i]!=i+1){bru=1;}
}
return (1-bru);
}
}
int replacement(int n, int a[], int c[]){
ll k = valid(n, a);
if(k==0){return 0;}
else {
int don=0;
val=0;
ans=1;
for(int i=0; i<n; i++){
if(b[i]!=i+1){val++; cha[val] = i; }
}
fin=val;
sort(cha+1, cha+val+1, cmp);
ok = n;
for(int i=1; i<=val; i++){
don++;
c[don-1] = cha[i]+1;
for(int j =1; j<= b[cha[i]]-ok-1; j++){
don++;
c[don-1] = ok+j;
ans *= (val-i+1);
ans %= p;
}
ok = b[cha[i]];
}
return don;
}
}
int countReplacement(int n, int a[]){
ll n1 = valid(n, a);
if(n1==0){ return 0;}
else {
val=0;
ans=1;
for(int i=0; i<n; i++){
if(b[i]!=i+1){val++; cha[val] = i; }
}
sort(cha+1, cha+val+1, cmp);
ok = n;
for(ll i=1; i<=val; i++){
ans *= pow(val-i+1, b[cha[i]]-ok-1);
ans %= p;
ok = b[cha[i]];
}
int tt=1;
for(int i=0; i<n; i++){
if(a[i]<=n){tt=0;}
}
if(tt==1){ans *= n; ans %= p;}
return ans;
}
}
