#include<fstream>
#include<math.h>
#include<stdlib.h>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,c[100],diagdr[100],diagst[100],l[100],nr,sol[100],sw=0;
void backt(int k){
    int i,j;
    if (k>n){
        if (sw==0){
            for (j=1;j<=n;j++)
                fout<<c[j]<<" ";
            fout<<'\n';
            sw=1;
        }
        nr++;
    }
      else
        for (i=1;i<=n;i++){
            c[k]=i;
            if (l[i]==0 && diagdr[n+k-i]==0 && diagst[i+k]==0){
                l[i]=1;
                diagst[i+k]=1;
                diagdr[n+k-i]=1;
                backt(k+1);
                l[i]=0;
                diagst[i+k]=0;
                diagdr[n+k-i]=0;
            }
        }
}
int main(){
    fin>>n;
    fin.close();
    backt(1);
    fout<<nr;
    fout.close();
    return 0;
}