#include <fstream>
#define SIZE 100
using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
long n, ctr;
short e[SIZE*2], f[SIZE*2], c[SIZE], perm[SIZE];
void backtrack(short line)
{
    if(line>n)
    {
        ++ctr;
        if(ctr==1)
        {
            for(short i=1; i<=n; ++i) out<<perm[i]<<' ';
            out<<'\n';
        }
        return;
    }
    for(short i=1; i<=n; ++i)
    {
        if(!c[i]&&!e[i-line+SIZE]&&!f[i+line+SIZE])
        {
            perm[line]=i;
            c[i]=1;
            e[i-line+SIZE]=1;
            f[i+line+SIZE]=1;
            backtrack(line+1);
            c[i]=0;
            e[i-line+SIZE]=0;
            f[i+line+SIZE]=0;
        }
    }
}
int main()
{
    in>>n;
    ctr=0;
    backtrack(1);
    out<<ctr<<endl;
    in.close(); out.close();
    return 0;
}