#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];

int Verificare(int lin,int col)
{ int i;
  for(i=1;i<=lin-1;i++)
       if(lin-i==abs(col-x[i]))
           return 0;
  return 1;
}

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 && Verificare(k,i)==1)
        { viz_col[i]=1; x[k]=i;
          if(k==n)
             { if(ct==0)
                   {ct++; Solutie();}
               else ct++;
             }
          else Back(k+1);
          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;
}