#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,j,v[15],l,i;
bool valid[15][15],ok;
void bt(int i)
{
    int j,z,d;
    if (i==n+1)
    {
        if (ok==false)
        for (j=1;j<=n;j++)
        g<<v[j]<<' ',ok=true;
        l++;
    }
    else
    for (j=1;j<=n;j++)
    if (valid[i][j])
    {
        v[i]=j;
        for (z=i+1;z<=n;z++)
        valid[z][j]=false;
        for (z=i+1,d=j+1;z<=n && d<=n;z++,d++)
        valid[z][d]=false;
        for (z=i+1,d=j-1;z<=n && d>=1;z++,d--)
        valid[z][d]=false;
        bt(i+1);
        for (z=i+1;z<=n;z++)
        valid[z][j]=true;
        for (z=i+1,d=j+1;z<=n && d<=n;z++,d++)
        valid[z][d]=true;
        for (z=i+1,d=j-1;z<=n && d>=1;z++,d--)
        valid[z][d]=true;
    }
}
int main()
{

    f>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
             valid[i][j]=true;
    bt(1);
    g<<'\n'<<l;
    return 0;
}