#include "gondola.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define fip(a,b) for(ll i = a ; i < b; i++)
#define fjp(a,b) for(ll j = a ; j < b; j++)
#define fp(k,a,b) for(ll k = a ; k < b; k++)
#define fin(a,b) for(ll i = a ; i >= b; i---)
#define fjn(a,b) for(ll j = a ; j >= b; j---)
#define fn(k,a,b) for(ll k = a ; k >= b; k---)
#define fx(a) for(auto x:a)
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define nli "\n"
#define test ll t;cin>>t;while(t--)
#define srt(a) sort(a.begin(),a.end())
#define all(a) a.begin(),a.end()
void _printn(int a){cerr<<a<<" ";}
void _printn(ll a){cerr<<a<<" ";}
void _printn(bool a){cerr<<a<<" ";}
void _printn(double a){cerr<<a<<" ";}
template<class T> void _printn(vector<T> a);
template<class T,class V> void _printn(pair<T,V> a);
template<class T> void _printn(vector<T> a){
cerr<<"[ ";
fx(a){
_printn(x);cerr<<" ";
}
cerr<<"]";
}
template<class T,class V> void _printn(pair<T,V> a){
cerr<<"( ";
_printn(a.ff);
cerr<<",";
_printn(a.ss);
cerr<<")";
}
#ifdef SAMI
#define debug(x) cerr<<#x<<" : ";_printn(x);cerr<<nli;
#define debg() cerr<<nli;
#else
#define debug(x)
#define debg()
#endif
const ll mx = 3e5 + 5;
const ll mod = 1e9 + 9;
bool f = 0;
ll n,m,res,cnt,sum,tp,tp2,tptp,ans;
bool mark[mx];
ll b[mx];
ll rs = 0;
ll mod_power(ll aa,ll bb){
rs = 1;
aa %= mod;
bb %= mod-1;
while(bb>=1){
if(bb&1){
rs *= aa;
rs %= mod;
}
bb >>= 1;
aa *= aa;
aa %= mod;
// debug(aa);
// debug(bb);
// debug(rs);
// debg();
}
return rs;
}
int valid(int n, int inputSeq[]){
tp = -1;
fip(0,n){
if(tp!=-1)tp++;
if(tp>n)
tp = 1;
if(inputSeq[i] <= n){
if(tp==-1){
tp = inputSeq[i];
}else if(tp!=inputSeq[i])
return 0;
} else{
if(mark[inputSeq[i]]) return 0;
mark[inputSeq[i]] = 1;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
ans = 0;
tp = -1;
vector<pi> lis;
fip(0,n){
if(tp!=-1)tp++;
if(tp>n)
tp = 1;
if(gondolaSeq[i] <= n){
if(tp==-1){
tp = gondolaSeq[i];
}else if(tp!=gondolaSeq[i])
return 0;
}
}
if(tp==-1)tp = 1;
else{
tp += 1;
if(tp > n) tp = 1;
}
fip(0,n){
b[i] = tp;
if(tp!=gondolaSeq[i])
lis.push_back({gondolaSeq[i],tp});
tp++;
if(tp>n)
tp = 1;
}
sort(lis.begin(),lis.end(),[](const pi aa,const pi bb){
return aa.ff > bb.ff;
});
debug(lis);
vi v;
fip(0,lis.size()){
if(i+1<lis.size())
tp = lis[i+1].ff+1;
else
tp = n+1;
cnt = 0;
while(lis[i].ff > tp){
ans ++;
v.push_back(lis[i].ff-1);
lis[i].ff--;
}
ans ++;
v.push_back(lis[i].ss);
}
// debug(v);
reverse(v.begin(),v.end());
fip(0,ans)
replacementSeq[i] = v[i];
f = 1;
tp2 = n+1;
fx(v){
fip(0,n){
if(b[i]==x){
// debug(x);
b[i] = tp2;
tp2++;
// debug(b[i]);
break;
}
}
}
fip(0,n)
if(b[i]!=gondolaSeq[i])
f = 0;
// fip(0,n)
// cout<<b[i]<<" ";
// cout<<nli;
return ans;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
tp = -1;
vi v;
f = 1;
set<ll> st;
fip(0,n){
if(tp!=-1)tp++;
if(tp>n)
tp = 1;
if(inputSeq[i] <= n){
if(tp==-1){{
f= 0;
tp = inputSeq[i];
}
}else if(tp!=inputSeq[i])
return 0;
} else{
if(st.find(inputSeq[i])!=st.end()) return 0;
st.insert(inputSeq[i]);
v.push_back(inputSeq[i]);
}
}
srt(v);
ans = 1;
res = v.size();
tp = n;
// debug(v);
fx(v){
tp2 = x - tp - 1;
// debug(res);
// debug(tp2);
ans = ans * mod_power(res,tp2);
// debug(mod_power(res,tp2));
ans %= mod;
tp = x;
res--;
}
if(f){
ans *= n;
ans %= mod;
}
return ans;
}
#ifdef SAMI
int gondolaSequence[100001];
int replacementSequence[250001];
int main()
{
freopen("input1.txt","r",stdin);
freopen("output1.txt","w",stdout);
freopen("error1.txt","w",stderr);
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
