#include "gondola.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const long long mod = 1000000009 ;
const int mod1 = 998244353 ;
const int N = 2e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int valid(int n, int a[]){
int pos = 0 ;
FOR( i , n ){
if( a[ i ] <= n ){
pos = i ; break ;
}
}
ma.clear() ;
FOR( i , n ) if( a[ i ] == 0 ){
return 0 ;
}
FOR( i , n ){
if( ma[ a[ i ] ] == 1 ) return 0 ;
ma[ a[ i ] ] = 1 ;
}
int j = pos , cur = a[ pos ] ;
while( true ){
if( a[ j ] <= n ){
if( a[ j ] != cur ) return 0 ;
}
cur ++ ; if( cur == n + 1 ) cur = 1 ;
j ++ ; j %= n ;
if( j == pos ) break ;
}
return 1 ;
}
int replacement(int n, int a[], int replacementSeq[]){
int mx = 0 , mn = INT_MAX ;
int b[ n ] ;
set < int > se ;
FOR( i , n ){
mn = min( mn , a[ i ] ) ;
mx = max( mx , a[ i ] ) ;
}
for( int j = n + 1 ; j <= mx ; j ++ ) se.insert( j ) ;
// FOR( i , n ){
// if( a[ i ] > n ) se.erase( se.find( a[ i ] ) ) ;
// }
if( mn > n ){
FOR( i , n ) b[ i ] = i + 1 ;
}
else{
int pos = 0 ;
FOR( i , n ){
if( a[ i ] <= n ){
pos = i ; break ;
}
}
int j = pos , cur = a[ pos ] ;
while( true ){
b[ j ] = cur ;
cur ++ ; if( cur == n + 1 ) cur = 1 ;
j ++ ; j %= n ;
if( j == pos ) break ;
}
}
int cnt = 0 ;
vector < pair < int , int > > v ;
FOR( i , n ){
if( a[ i ] == b[ i ] ) continue ;
v.pb( { a[ i ] , b[ i ] } ) ;
}
sort( v.begin() , v.end() ) ;
for( auto x : v ){
int lst = x.s ;
int nd = x.f ;
while( true ){
int x = *se.begin() ;
replacementSeq[ cnt ] = lst ;
cnt ++ ;
lst = x ;
se.erase( se.begin() ) ;
//cout << x << " " << nd << endl ;
if( x == nd ) break ;
}
}
return cnt ;
}
long long pp( int X, int Y, int p)
{
if( Y == 0 ) return 1 ;
long long x = X , y = Y ;
int res = 1;
while (y > 0) {
if (y % 2 == 1)
res = (res * x % p );
y = y >> 1;
x = (x * x % p );
}
return res % p;
}
vector < int > v ;
int b[ N ] ;
int countReplacement(int n, int a[]){
// se.clear() ;
v.clear();
ma.clear() ;
long long ans = 1 ;
int x = valid( n , a ) ;
if( x == 0 ) return 0 ;
int mx = 0 ;
FOR( i , n ) mx = max( mx , a[ i ] ) ;
if( mx <= n ) return 1 ;
int mn = INT_MAX ;
FOR( i , n ){
mn = min( mn , a[ i ] ) ;
mx = max( mx , a[ i ] ) ;
}
// for( int j = n + 1 ; j <= mx ; j ++ ) se.pb( j ) ;
if( mn > n ){
ans = n ;
FOR( i , n ) b[ i ] = i + 1 ;
}
else{
int pos = 0 ;
FOR( i , n ){
if( a[ i ] <= n ){
pos = i ; break ;
}
}
int j = pos , cur = a[ pos ] ;
while( true ){
b[ j ] = cur ;
cur ++ ; if( cur == n + 1 ) cur = 1 ;
j ++ ; j %= n ;
if( j == pos ) break ;
}
}
int cnt = 0 ;
FOR( i , n ){
if( a[ i ] == b[ i ] ) continue ;
v.pb( a[ i ] ) ;
}
sort( v.begin() , v.end() ) ;
long long lf = v.size() ;
int st = 0 ;
int lst = n + 1 ;
for( auto x : v ){
// int lst = x.s ;
int nd = x ;
long long y = pp( lf , nd - lst , mod ) ;
ans = ans * y ;
ans %= mod ;
lst = nd + 1 ;
lf -- ;
}
ans %= mod ;
int pas = ans ;
return ans ;
}
//int gondolaSequence[100001];
//int replacementSequence[250001];
//
//int main() {
// int i, n, tag;
// int nr;
// assert(scanf("%d", &tag) == 1);
// assert(scanf("%d", &n) == 1);
// for (i = 0; i < n; i++)
// assert(scanf("%d", &gondolaSequence[i]) == 1);
//
// switch (tag) {
// case 1:
// case 2:
// case 3:
// printf("%d\n", valid(n, gondolaSequence));
// break;
//
// case 4:
// case 5:
// case 6:
// nr = replacement(n, gondolaSequence, replacementSequence);
// printf("%d ", nr);
// if (nr > 0) {
// for (i = 0; i < nr - 1; i++)
// printf("%d ", replacementSequence[i]);
// printf("%d\n", replacementSequence[nr - 1]);
// } else
// printf("\n");
// break;
//
// case 7:
// case 8:
// case 9:
// case 10:
// printf("%d\n", countReplacement(n, gondolaSequence));
// break;
// }
//
// return 0;
//}
