#include <stdio.h>
#define MAXN 13

char okL[MAXN], okC[MAXN], okDp[2 * MAXN - 1], okDs[2 * MAXN - 1];
//0 = ok
//1 = !ok
//n-l+c-1 = nr. Dp pentru elem(l, c)
//l+c = nr. Ds pentru elem(l, c)
int nrConf;

int dame[MAXN];

int verify( int l, int c, int n ) {
  if ( okL[l] == 0 && okC[c] == 0 && okDp[n - l + c - 1] == 0 && okDs[l + c] == 0 ) {
    return 1; 	                                                     
  }
  return 0;
}

FILE *fin, *fout;

void backtrack( int l, int n ) {
  int c, i;
   
  if ( l == n ) {
    if ( nrConf == 0 ) {
	  for ( i = 0; i < n; ++i ) {
		fprintf( fout, "%d ", dame[i] + 1 );
	  }
	}
	++nrConf;
  } else {
    for ( c = 0; c < n; ++c ) {
	  if ( verify( l, c, n ) ) {
	    dame[l] = c;
	    okL[l] = 1;
	    okC[c] = 1;
	    okDp[n - l + c - 1] = 1;
	    okDs[l + c] = 1;
        backtrack( l + 1, n );
	    okL[l] = 0;
	    okC[c] = 0;
        okDp[n - l + c - 1] = 0;
	    okDs[l + c] = 0;
	  }
	}
  }
}

int main() {
  fin = fopen( "damesah.in", "r" );
  fout = fopen( "damesah.out", "w" );
  int n;
  
  fscanf( fin, "%d", &n );
  backtrack( 0, n );
  fprintf( fout, "\n%d", nrConf );
  fclose( fin );
  fclose( fout );
  return 0;
}