#include <stdio.h>

#define MAX_N 13
#define SHIFT MAX_N

char fl[MAX_N], fp[MAX_N + SHIFT], fs[MAX_N + SHIFT], n;

int sol( int lin ) {
  int col, rez = 0;

  if ( lin == n + 1 )
    return 1;

  for ( col = 1; col <= n; col++ ) {
    if ( !fl[col] && !fp[col - lin + SHIFT] && !fs[col + lin - 1] ) {
      fl[col] = fp[col - lin + SHIFT] = fs[col + lin - 1] = 1;
      rez += sol( lin + 1 );
      fl[col] = fp[col - lin + SHIFT] = fs[col + lin - 1] = 0;
    }
  }

  return rez;
}

int main() {
  FILE *fin, *fout;
  int rez, i;

  fin = fopen( "damesah.in", "r" );
  fscanf( fin, "%hhd", &n );
  fclose( fin );

  rez = sol( 1 );
  fout = fopen( "damesah.out", "w" );
  i = n & 1 == 1 ? 1 : 2;
  while ( i <= n ) {
    fprintf( fout, "%d ", i );
    i += 2;
  }
  i = n & 1 == 1 ? 2 : 1;
  while ( i <= n ) {
    fprintf( fout, "%d ", i );
    i += 2;
  }
  fprintf( fout, "\n%d\n", rez );
  fclose( fout );

  return 0;
}