#include <bits/stdc++.h>
using namespace std;

ifstream fin ("damesah.in");
ofstream fout("damesah.out");

const int dim=100,mij=50;

int n,fv[dim],sol[dim],ok,cnt;
bool st[dim],dr[dim];

void afisare(){
    cnt++;
    if(!ok){
        for(int i=1;i<=n;i++){
            fout<<sol[i]<<' ';
        }
            fout<<'\n';
        ok=1;
    }
}

void backtracking(int pas){
    for(int i=1;i<=n;i++){
        if(!fv[i]&&!st[mij+pas-i]&&!dr[mij+pas+i]){
            fv[i]=st[mij+pas-i]=dr[mij+pas+i]=1;
            sol[pas]=i;
            if(pas==n){
                afisare();
            }
            else{
                backtracking(pas+1);
            }
            fv[i]=st[mij+pas-i]=dr[mij+pas+i]=0;
        }
    }
}

signed main(){
    fin>>n;
    backtracking(1);
    fout<<cnt;
}