#include <fstream>

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

    f>>n;
    bt(1);
    g<<'\n'<<l;
    return 0;
}