#include <fstream>
#define N 15
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n,x[N],ct,viz_lin[N],sol[N],viz_col[N],diag1[2*N],diag2[2*N];


void Solutie()
{ int i;
  for(i=1;i<=n;i++)
      sol[i]=x[i];
}

void Back(int k)
{ int i;
  for(i=1;i<=n;i++)
     if(viz_col[i]==0 && diag1[n-(k-i)]==0 && diag2[2*n-(k+i)+1]==0)
        {
            viz_col[i]=1;
            x[k]=i;
            diag1[n-(k-i)]=1;
            diag2[2*n-(k+i)+1]=1;
          if(k==n)
             { if(ct==0)
                   {ct++; Solutie();}
               else ct++;
             }
          else Back(k+1);
          diag1[n-(k-i)]=0;
          diag2[2*n-(k+i)+1]=0;
          viz_col[i]=0;
        }
}

void Afisare()
{ int i;
  for(i=1;i<=n;i++)
      fout<<sol[i]<<" ";
  fout<<"\n"<<ct;
}

int main()
{   fin>>n;
    Back(1);
    Afisare();
    return 0;
}