#include<fstream>
using namespace std;

int rs,n,a[15],c[20],x[20],y[20];
  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)
             { if (c[i]==0 && x[nivel+i]==0 && y[nivel+n-i]==0)
                { a[nivel]=i;
                  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;
}