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

int nr=0;
int a[15],n;
bool d[15][15],c[15],d2[15][15];

void afisare ()
{
    for (int i=1;i<=n;i++) g<<a[i]<<" ";
    g<<"\n";

}

int check (int col, int lin)
{

    int pr=0;
   if (c[col]==0) pr++;
   if (lin>col)
   {
       if (d[lin-col][0]==0) pr++;
   }
   else
   {
       if (d[0][col-lin]==0) pr++;
   }
   if (n-lin+1>col)
   {
       if (d2[n-lin-col+1][0]==0) pr++;
   }
   else
   {
       if (d2[n+1][lin+col-n-1]==0) pr++;
   }
     return pr;
}



void Back (int k)
{
    int z,i;
    if (k<=n)
    {
    for (i=1;i<=n;i++)
    {
       int lin=k;
       int col=i;
     if (nr==0)  a[k]=i;
        z=check(i, k);
        if (z==3)
        {
            c[i]=1;
            if (k>i) d[k-i][0]=1;
            else d[0][i-k]=1;
            if (n-lin+1>col) d2[n-lin-col+1][0]=1;
            else d2[n+1][lin+col-n-1]=1;
            Back (k+1);
            c[i]=0;
            if (k>i) d[k-i][0]=0;
            else d[0][i-k]=0;
             if (n-lin+1>col) d2[n-lin-col+1][0]=0;
            else d2[n+1][lin+col-n-1]=0;
        }
    }
}
    else
    {
      if (nr==0)  afisare();
        nr++;
    }
}


int main()
{
f>>n;
Back (1);
//int x=check (1,1);
//cout<<x<<"\n";
g<<nr;


    return 0;
}