#include <bits/stdc++.h>
#define DM 50
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
bitset<DM>lin,col,d1,d2;
int v[DM],n,cont;
bool ok=0;

void afis(){
    for(int i=1;i<=n;++i) fout<<v[i]<<" ";
}

void bck(int step){
    if(step==n+1){
        if(!ok) afis(),ok=1,cont=1;
        else cont++;
        return;
    }
    for(int i=1;i<=n;++i){
        if(!lin[i] && !col[step] && !d1[step+i] && !d2[step-i+n]){
            lin[i]=col[step]=d1[step+i]=d2[step-i+n]=1;
            v[step]=i;
            bck(step+1);
            lin[i]=col[step]=d1[step+i]=d2[step-i+n]=0;
        }
    }
}

int main()
{
    fin>>n;
    bck(1);
    fout<<'\n'<<cont;
    return 0;
}