#include <stdio.h>

enum { NMAX = 13 };

int locp[NMAX], cocp[NMAX], d1ocp[2 * NMAX], d2ocp[2 * NMAX], poz[NMAX], sol[NMAX];

int n, nrsol, solgas;

void punedama(int i, int dameram) {
  if (dameram == 0) {
    nrsol++;
    if (!solgas) {
      for (i = 0; i < n; i++) {
        sol[i] = poz[i];
      }
      solgas = 1;
    }
    return;
  }
  if (i == n * n)
    return;
  int l = i / n, c = i % n;
  if (!locp[l] && !cocp[c] && !d1ocp[n - 1 + l - c] && !d2ocp[l + c]) {
    locp[l] = 1;
    cocp[c] = 1;
    d1ocp[n - 1 + l - c] = 1;
    d2ocp[l + c] = 1;
    poz[l] = c;
    punedama((l + 1) * n, dameram - 1);
    locp[l] = 0;
    cocp[c] = 0;
    d1ocp[n - 1 + l - c] = 0;
    d2ocp[l + c] = 0;
  }
  punedama(i + 1, dameram);
}

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

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

  punedama(0, n);

  fout = fopen("damesah.out", "w");
  for (i = 0; i < n; i++) {
    fprintf(fout, "%d ", sol[i] + 1);
  }
  fprintf(fout, "\n%d\n", nrsol);
  fclose(fout);

  return 0;
}