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

int niv,n,i[20],c[20],dp[100],ds[100],k;
void back(int niv){
    if(niv>n){
            if(k==0) {
        for(int j=1;j<=n;j++) out<<i[j]<<' '; out<<'\n';
            }
            k++;
    }

    for(i[niv]=1;i[niv]<=n;i[niv]++)
    if(c[i[niv]]==0 && dp[niv-i[niv]+n]==0 && ds[niv+i[niv]]==0) {
        c[i[niv]]=dp[niv-i[niv]+n]=ds[niv+i[niv]]=1;
        back(niv+1);
        c[i[niv]]=dp[niv-i[niv]+n]=ds[niv+i[niv]]=0;
    }
}

int main()
{   in>>n;
    back(1);
    out<<k<<'\n';
}