#include <fstream>

using namespace std;

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

int lvl,n,i[21],a[21],b[101],c[101],k;

void backtr(int lvl){
    if(lvl>n){
            if(k==0) {
        for(int j=1;j<=n;j++) fout<<i[j]<<' ';fout<<'\n';}k++;}
    for(i[lvl]=1;i[lvl]<=n;i[lvl]++)
    if(a[i[lvl]]==0 && b[lvl-i[lvl]+n]==0 && c[lvl+i[lvl]]==0) {
        a[i[lvl]]=b[lvl-i[lvl]+n]=c[lvl+i[lvl]]=1;
        backtr(lvl+1);
        a[i[lvl]]=b[lvl-i[lvl]+n]=c[lvl+i[lvl]]=0;
    }
}

int main()
{
    fin>>n;
    backtr(1);
    fout<<k<<'\n';
}