#include<fstream>
using namespace std;
 
int rs=0,n,a[15],c[20],x[30],y[30];

ifstream cin("damesah.in");
ofstream cout("damesah.out");

void dame(int nivel){ 
   int i;
   if (nivel==n+1)
   {
     rs++;
     if (rs==1) 
	   for (i=1;i<=n;++i) 
	     cout<<a[i]<<' ';
   }
   else 
     for (i=1;i<=n;++i){
      a[nivel]=i;   
       if (c[i]==0 && x[nivel+i]==0 && y[nivel+n-i]==0)
       { 
         c[i]=x[nivel+i]=y[nivel+n-i]=1;
         dame(nivel+1);
         c[i]=x[nivel+i]=y[nivel+n-i]=0;
      }               
     } 
 } 
  
int main()
{   
    cin>>n;
    dame(1);
    cout<<'\n'<<rs;
   
  return 0;
}