#include <fstream>
#include <algorithm>

using namespace std;

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

#define DIM 15

int n, total;
int col[DIM + 1], sol[DIM + 1], ans[DIM + 1], diag1[2 * DIM + 1], diag2[2 * DIM + 1];

static inline void Solutie() {
  if(total == 0)
    for(int i = 1; i <= n; i++)
      ans[i] = sol[i];
  total++;
}

static inline void Back(int k) {
  if(k > n)
    Solutie();
  else for(int i = 1; i <= n; i++) {
    sol[k] = i;     //pozitia pe care l pun pe i;
    col[i]++;             //sa nu am mai multe elemente pe coloana i;
    diag1[i + k]++;
    diag2[DIM + k - i]++;

    if(col[i] == 1 && diag1[i + k] == 1 && diag2[DIM + k - i] == 1)
      Back(k + 1);

    col[i]--;
    diag1[i + k]--;
    diag2[DIM + k - i]--;
  }
}

int main() {
  fin >> n;

  total = 0;
  Back(1);

  for(int i = 1; i <= n; i++)
    fout << ans[i] << " ";
  fout << '\n' << total;

  return 0;
}