#include <bits/stdc++.h>
using namespace std;
const int NMAX = 20;
int n,st[NMAX],cnt,first[NMAX],vf_col[NMAX],vf_diag[2][2*NMAX];

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

void bkt(int pas){
  if(pas == n+1){
    cnt++;
    if(cnt == 1){
      memcpy(first, st, sizeof(st));
    }
  }else{
    for(int i = 1; i <= n; i++){
      if(vf_col[i] == 0 && vf_diag[0][pas+i] == 0 && vf_diag[1][pas-i+n] == 0){
        st[pas] = i;
        vf_col[i] = 1;
        vf_diag[0][pas+i] = 1;
        vf_diag[1][pas-i+n] = 1;

        bkt(pas+1);

        vf_col[i] = 0;
        vf_col[i] = 0;
        vf_diag[0][pas+i] = 0;
        vf_diag[1][pas-i+n] = 0;
      }
    }
  }
}

int main() {
  fin >> n;
  bkt(1);
  for(int i = 1; i <= n; i++){
    fout << first[i] << " ";
  }
  fout << "\n";
  fout << cnt;
  return 0;
}