#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, sol[15], folosit[15], d1[50], d2[50], nrw;
char okfirst;
void bkt(int k)
{
    if(k>n)
    {
        if(okfirst==0)
        {for(int i=1;i<=n;i++)
            fout<<sol[i]<<' ';
        fout<<'\n';
        okfirst=1;
        }
        nrw++;
    }
    for(int i=1;i<=n;i++)
    {
        if(folosit[i]==0&&d1[i+k]==0&&d2[i-k]==0)
        {
            folosit[i]=d1[i+k]=d2[i-k]=1;
            sol[k]=i;
            bkt(k+1);
            folosit[i]=d1[i+k]=d2[i-k]=0;
        }
    }
}
int main()
{
    fin>>n;
    bkt(1);
    fout<<nrw;
    return 0;
}