#include <bits/stdc++.h>
#define long long long
#include "gondola.h"
using namespace std;
const long M = 1e9+9;
int valid(int n, int inputSeq[]) {
for(int i = 0, st = -n-1; i < n; ++i, ++st) {
if(st == n+1) st = 1;
if(inputSeq[i] <= n) {
if(st < 0) st = inputSeq[i];
else if(st != inputSeq[i]) return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int sz = 0, mx = *max_element(gondolaSeq, gondolaSeq + n);
set<int> S;
for(int i = 0; i < n; ++i) S.emplace(gondolaSeq[i]);
for(int i = 1; i <= mx; ++i)
if(S.find(i) == S.end()) replacementSeq[sz++] = i;
return sz;
}
//----------------------
int powMod(int a, int b) {
if(!a) return a;
int val = 1;
while(b) {
if(b & 1) val = (1ll * val * a) % M;
a = (1ll * a * a) % M;
b >>= 1;
}
return val;
}
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq)) return 0;
vector<int> V; V.emplace_back(n);
for(int i = 0; i < n; ++i) if(inputSeq[i] > n) V.emplace_back(inputSeq[i]);
if(V.size() == 1) return 1;
long ans = 0; int s = V.size();
sort(V.begin(), V.end());
for(int i = 1; i < s; ++i) ans = (ans + powMod(s - i, V[i] - V[i-1] - 1)) % M;
return ans;
}
