#include<iostream>
#include<fstream>
#include<math.h>
#define dimmax 100
using namespace std;
int s[dimmax], n, k, sol=0;
ifstream f("damesah.in");
ofstream g("damesah.out");

void init( )  {s[k]=0; }

int succesor ( ){if (s[k]<n){s[k]++; return 1; }  return 0; }

bool valid ( )
{for (int i=1; i<k; i++)
if((s[i]==s[k]) || (fabs(s[k]-s[i])== k-i))return 0;return 1; }

int solutie ( ) { if (k==n)   return 1; return 0;}

void afisare()		//afişare liniară
{for(int i=1;i<=n;i++)
 if (sol==1) g<<s[i]<<" "; //g<<'\t';
 }

void bkt( )
{ int as, ev;k=1;
 init();while(k>0)
{as=1;ev=0; while(as&&!ev) {as=succesor(); if(as!=0)  ev=valid();}
 if(as!=0) if(solutie())  {sol++;afisare();}
                else   {k++;init();}
    else k--;}
g<<'\n'<<sol;}
int main ( )
{ f>>n; bkt( ); return 0;}