#include <bits/stdc++.h>
using namespace std;
//#define HOME
#ifndef HOME
#include "gondola.h"
#endif // HOME
int valid(int n, int inputSeq[]) {
int mn = 0;
map <int, int> freq;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < inputSeq[mn])
mn = i;
freq[inputSeq[i]]++;
if (freq[inputSeq[i]] > 1) return 0;
}
rotate (inputSeq, inputSeq + mn, inputSeq + n);
int val = inputSeq[0];
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
if (val != inputSeq[i])
return 0;
}
val++;
}
return 1;
}
//----------------------
const int max_n = 25e4;
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int mn = 0;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] < gondolaSeq[mn])
mn = i;
}
if (gondolaSeq[mn] <= n)
rotate (gondolaSeq, gondolaSeq + (n + mn - gondolaSeq[mn] + 1) % n, gondolaSeq + n);
int l = 0;
vector <int> pos (1 + max_n);
int mx = 0;
for (int i = 0; i < n; i++) {
pos[gondolaSeq[i]] = i + 1;
if (gondolaSeq[i] > gondolaSeq[mx])
mx = i;
}
int valmax = gondolaSeq[mx];
int cur = mx + 1;
for (int i = n + 1; i <= valmax; i++) {
if (i == valmax || pos[i] == 0)
replacementSeq[l++] = cur, cur = i;
else
replacementSeq[l++] = pos[i];
}
return l;
}
//----------------------
const int MOD = 1e9 + 9;
int mult (int a, int b) {
return 1ll * a * b % MOD;
}
int lgput (int a, int b) {
int ans = 1;
while (b > 0) {
if (b & 1)
ans = mult (ans, a);
a = mult (a, a);
b /= 2;
}
return ans;
}
int countReplacement(int n, int inputSeq[]) {
if (not valid (n, inputSeq))
return 0;
bool fix = false;
int mn = 0;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < inputSeq[mn])
mn = i;
}
if (inputSeq[mn] <= n)
rotate (inputSeq, inputSeq + (n + mn - inputSeq[mn] + 1) % n, inputSeq + n), fix = true;
vector <int> rep;
for (int i = 0; i < n; i++)
if (inputSeq[i] > n)
rep.push_back (inputSeq[i]);
sort (rep.begin (), rep.end ());
int sz = rep.size ();
int lst = n, ans = 1;
for (int i = 0; i < sz; i++) {
ans = mult (ans, lgput (sz - i, rep[i] - lst - 1));
lst = rep[i];
}
if (fix)
return ans;
return mult (ans, n);
}
#ifdef HOME
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;
}
#endif // HOME
/**
8
14
6 94 8 9 10 93 12 13 95 1 2 3 4 5
**/
