#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
//#define TEST
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+9;
#ifdef TEST
int gondolaSequence[100001];
int replacementSequence[250001];
#endif
int add(int a, int b){
return (a+b)%mod;
}
int mul(int a, int b){
return (a*1LL*b)%mod;
}
int po(int a, int b){
if (b == 0) return 1;
if (b%2 == 0) return po(mul(a, a), b/2);
return mul(a, po(mul(a, a), b/2));
}
int valid(int n, int arr[]){
int pos = -1;
for (int i = 0; i < n; i++)
if (arr[i] <= n) pos = i;
if (pos != -1){
int cur = arr[pos];
for (int i = 0; i < n; i++){
if (arr[pos] <= n && arr[pos] != cur)
return 0;
cur = cur%n+1;
pos = (pos+1)%n;
}
}
sort(arr, arr+n);
for (int i = 0; i < n-1; i++)
if (arr[i] == arr[i+1])
return 0;
return 1;
}
//----------------------
int replacement(int n, int arr[], int out[]){
vector<ii> vec;
int pos = -1, nex = n+1, m = 0, cur;
for (int i = 0; i < n; i++)
if (arr[i] <= n) pos = i;
if (pos == -1)
pos = 0, cur = 1;
else
cur = arr[pos];
for (int i = 0; i < n; i++){
if (arr[pos] > n)
vec.pb(mp(arr[pos], cur));
pos = (pos+1)%n;
cur = cur%n+1;
}
sort(vec.begin(), vec.end());
for (int i = 0; i < vec.size(); i++)
while (vec[i].fi > vec[i].se)
out[m++] = vec[i].se, vec[i].se = nex++;
return m;
}
//----------------------
int countReplacement(int n, int arr[]){
vector<int> vec;
if (!valid(n, arr))
return 0;
vec.pb(n);
for (int i = 0; i < n; i++)
if (arr[i] > n) vec.pb(arr[i]);
int ans = 1;
sort(vec.begin(), vec.end());
for (int i = 1; i < vec.size(); i++)
ans = mul(ans, po(vec.size()-i, vec[i]-vec[i-1]-1));
if (vec.size() == n+1)
ans = mul(ans, n);
return ans;
}
#ifdef TEST
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\n", 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;
}
#endif
/*
3 5
10 4 3 11 12
3 7
2 3 4 9 6 7 1
6 7
2 3 4 9 6 7 1
10 2
3 4
*/
