#include <fstream>
#include <vector>
using namespace std;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
vector<int>rasp;
vector<bool>d1,d2,col;
int cont=0;
int n;
bool ok=true;
void backtracking(int x){
if(x==n+1){
 if(ok){
    for(int i=1;i<=n;i++){
        cout<<rasp[i]<<" ";
    }
    cout<<'\n';
    cont++;
    ok=false;
    return;
 }else{
    cont++;
    return;
 }
}
for(int i=1;i<=n;i++){
    if(!d1[i+x] || !d2[x-i+n] || !col[i]){
        continue;
    }
    rasp[x]=i;
    d1[i+x]=false;
    d2[x-i+n]=false;
    col[i]=false;
    backtracking(x+1);
    d1[i+x]=true;
    d2[x-i+n]=true;
    col[i]=true;
}
}

void read(){
cin>>n;
d1.resize(2*n+1,true);
d2.resize(2*n+1,true);
col.resize(2*n+1,true);
rasp.resize(n+1);
}
void solve(){
read();
backtracking(1);
cout<<cont;
}
int main()
{
   int t;
   t=1;
   while(t--){
    solve();
   }
    return 0;
}