#include<fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,k,ok;
int v[30],J[30],IJ[30],JI[30];

int verif(int pas,int i){
    if(IJ[pas-i+n]==0&&JI[pas+i]==0)
        return 1;
    return 0;
}

void perm(int pas){

    if(pas>n){
        ok++;
        if(ok==1){
            for(int i=1;i<=n;i++){
                fout<<v[i]<<" ";
            }
            fout<<"\n";
        }
    }

    for(int i=1;i<=n;i++){
        if(verif(pas,i) && J[i]==0){
            J[i]=IJ[pas-i+n]=JI[pas+i]=1;
            v[pas]=i;
            ///
            perm(pas+1);
            ///
            J[i]=IJ[pas-i+n]=JI[pas+i]=0;
        }
    }
    return;
}


int main(){
    fin>>n;perm(1);fout<<ok;
    return 0;
}