#include <bits/stdc++.h>
using namespace std;
const int NMAX = 13;

ifstream fin( "damesah.in" );
ofstream fout( "damesah.out" );

int ans[NMAX+1];
int sol = 0;
int n;
int v[NMAX+1];
bool ocupCol[NMAX+1];
bool ocupDiag1[2*NMAX+1];
bool ocupDiag2[2*NMAX+1];

void bkt( int lin ) {
  int i, col;
  if( lin == n + 1 ) {
    if( sol == 0 ) {
      for( i = 1; i <= n; i++ )
        ans[i] = v[i];
    }
    sol++;
  }
  else {
    for( col = 1; col <= n; col++ ) {
      if( !ocupCol[col] && !ocupDiag1[lin+col-1] && !ocupDiag2[lin-col+n] ) {
        ocupCol[col] = ocupDiag1[lin+col-1] = ocupDiag2[lin-col+n] = true;
        v[lin] = col;
        bkt( lin + 1 );
        ocupCol[col] = ocupDiag1[lin+col-1] = ocupDiag2[lin-col+n] = false;
      }
    }
  }
}
int main() {
  int i;
  fin >> n;
  bkt( 1 );
  for( i = 1; i <= n; i++ )
    fout << ans[i] << " ";
  fout << "\n" << sol << "\n";
  return 0;
}