#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n, k, sol, s[30], coloana[30], diagp[30], diags[30];


void f (int nivel){

    /*
    for(int aux=1; aux<=nivel; aux++){
        cout<<s[aux]<<" ";
    }
    cout<<"\n";
    */

    if(nivel>n){
        sol++;
        if(sol==1){
            for(int i=1; i<=n; i++){
                fout<<s[i]<<" ";
            }
            fout<<"\n";
        }
    }
    for(int i=1; i<=n; i++){
        if(coloana[i]==0 && diagp[nivel-i+n]==0 && diags[nivel+i]==0){
            coloana[i]=1;
            diagp[nivel-i+n]=1;
            diags[nivel+i]=1;
            s[nivel]=i;
            f(nivel+1);
            coloana[i]=0;
            diagp[nivel-i+n]=0;
            diags[nivel+i]=0;
        }
    }
}


int main(){
    fin>>n;
    f(1);
    fout<<sol;
}