// This program was written
// by Mircea Rebengiuc
// for problem https://infoarena.ro/problema/damesah
// on 22.10.2022

#include <stdio.h>
#include <ctype.h>

#define magic_sauce inline __attribute__((always_inline))

const int MAXN = 13;

int n;
int nsol = 0;
int sol[MAXN];
int fsol[MAXN];

int fcol[MAXN];
int fdiag1[2 * MAXN]; // l + c
int fdiag2[2 * MAXN]; // l - c

void bkt( int l ){
  int c;
  
  if( l == n ){
    if( !nsol )
      for( c = 0 ; c < n ; c++ ) // refolosim c
        fsol[c] = sol[c];

    nsol++;
    return;
  }

  for( c = 0 ; c < n ; c++ )
    if( !( fcol[c] || fdiag1[l + c] || fdiag2[l - c + n - 1] ) ){
      fcol[c] = fdiag1[l + c] = fdiag2[l - c + n - 1] = 1;

      sol[l] = c;
      bkt( l + 1 );
      
      fcol[c] = fdiag1[l + c] = fdiag2[l - c + n - 1] = 0;
    }
}

int main(){
  FILE *fin  = fopen( "damesah.in",  "r" );
  FILE *fout = fopen( "damesah.out", "w" );

  int i;

  fscanf( fin, "%d", &n );

  for( i = 0 ; i < 2 * n ; i++ )
    fdiag1[i] = fdiag2[i] = 0;

  bkt( 0 );

  for( i = 0 ; i < n ; i++ )
    fprintf( fout, "%d ", 1 + fsol[i] );
  fprintf( fout, "\n%d\n", nsol );

  fclose( fin );
  fclose( fout );
  return 0;
}