#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
using namespace std;
typedef long long ll;
#include "gondola.h"
int valid(int n, int inputSeq[])
{
if (n == 1) return true;
vector <int> a(n);
set <int> diff;
bool big = true;
for (int i = 0; i < n; ++i) {
a[i] = inputSeq[i];
big &= (a[i] > n);
diff.insert(a[i]);
}
if ((int)diff.size() != n) return 0;
if (big) return true;
vector <int> nums(n, -1);
for (int i = 0; i < n; ++i) {
if (a[i] <= n) {
nums[i] = a[i] - 1;
}
}
for (int it = 0; it < 2; ++it) {
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) continue;
int j = (i + 1) % n;
if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
if (nums[j] != (nums[i] + 1) % n) {
return false;
}
}
}
return true;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = gondolaSeq[i];
--a[i];
}
vector <int> nums(n, -1);
for (int i = 0; i < n; ++i) {
if (a[i] < n) {
nums[i] = a[i];
}
}
for (int it = 0; it < 2; ++it) {
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) continue;
int j = (i + 1) % n;
if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
if (nums[j] != (nums[i] + 1) % n) {
assert(false);
}
}
}
for (int i = 0; i < n; ++i) if (nums[i] == -1) nums[i] = i;
vector <int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j) {
return a[i] < a[j];
});
int x = n;
int uk = 0;
auto add = [&] (int x) {
replacementSeq[uk++] = x + 1;
};
for (int i : p) {
while (nums[i] != a[i]) {
add(nums[i]);
nums[i] = x++;
}
}
return uk;
}
//----------------------
const int md = 1e9 + 9;
int mul(int a, int b) {
return ((ll)a * b) % md;
}
int power(int a, ll b) {
int res = 1;
while (b > 0) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
vector <int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = inputSeq[i];
--a[i];
}
vector <int> nums(n, -1);
for (int i = 0; i < n; ++i) {
if (a[i] < n) {
nums[i] = a[i];
}
}
for (int it = 0; it < 2; ++it) {
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) continue;
int j = (i + 1) % n;
if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
if (nums[j] != (nums[i] + 1) % n) {
assert(false);
}
}
}
vector <int> intr;
for (int i = 0; i < n; ++i) {
if (a[i] != nums[i]) {
intr.push_back(a[i]);
}
}
sort(intr.begin(), intr.end());
int ans = 1;
int lst = n;
for (int i = 0; i < (int)intr.size(); ++i) {
int cnt = intr[i] - lst;
ans = mul(ans, power((int)intr.size() - i, cnt));
lst = intr[i] + 1;
}
return ans;
}
#ifdef LOCAL
int gondolaSequence[100001];
int replacementSequence[250001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int i, n, tag;
int nr;
cin >> tag;
cin >> n;
for(i=0;i< n;i++)
cin >> gondolaSequence[i];
switch (tag){
case 1: case 2: case 3:
cout << valid(n, gondolaSequence) << '\n';
break;
case 4: case 5: case 6:
nr = replacement(n, gondolaSequence, replacementSequence);
cout << nr << '\n';
if (nr > 0)
{
for (i=0; i<nr-1; i++)
cout << replacementSequence[i] << " ";
cout << replacementSequence[nr-1] << "\n";
}
else printf("\n");
break;
case 7: case 8: case 9: case 10:
cout << countReplacement(n, gondolaSequence) << '\n';
break;
}
return 0;
}
#endif
