#include <fstream>
#include <bitset>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int diag[20][20],diag1[20][20],i,n,j,l,v[20],sol[20];
void fill(int i,int j)
{
    diag[i][j]=l;
    if (i+1<=n && j+1<=n)
        fill(i+1,j+1);
}
void fill1(int i,int j)
{
    diag1[i][j]=l;
    if (i+1<=n && j-1>=1)
        fill1(i+1,j-1);
}
bitset <25> o,p,c;
bool ok=false;
long long nrsol;
void bt(int i)
{
    int j;
    if (i==n+1)
    {
        nrsol++;
      if (ok==false)
        {for (j=1;j<=n;j++)
        sol[j]=v[j];
        ok=true;
        }
    }
    else
        for (j=1;j<=n;j++)
        if (p[diag[i][j]]==false && o[diag1[i][j]]==false && c[j]==false)
        {
            p[diag[i][j]]=true;
            o[diag1[i][j]]=true;
            c[j]=true;
            v[i]=j;
            bt(i+1);
            p[diag[i][j]]=false;
            o[diag1[i][j]]=false;
            c[j]=false;
        }

}
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
         for (j=1;j<=n;j++)
         if (diag[i][j]==0)
         {
             l++;
             fill(i,j);
         }
         l=0;
    for (i=1;i<=n;i++)
        for (j=n;j>=1;j--)
        if (diag1[i][j]==0)
    {
        l++;
        fill1(i,j);
    }
    bt(1);
    for (i=1;i<=n;i++)
        g<<sol[i]<<' ';
        g<<'\n'<<nrsol;
    return 0;
}