/**
Diagonale:
    1 2 3 4
    -------
1 | 4 3 2 1
2 | 5 4 3 2
3 | 6 5 4 3
4 | 7 6 5 4
Antidiagonale:
    1 2 3 4
    -------
1 | 1 2 3 4
2 | 2 3 4 5
3 | 3 4 5 6
4 | 4 5 6 7
 **/
#include <stdio.h>

#define MAX_N 13

FILE *f;

int n;
char s[MAX_N];
short col;
unsigned long long D;
int numSol;

void placeQueen(int q) {
  if (q == n) {
      if (++numSol <= 1) {
        for (int i = 0; i < n; i++) {
          fprintf(f, "%d ", 1 + s[i]);
        }
        fputc('\n', f);
      }
  } else {
    short c;
    unsigned long long tmp;
    for (int i = 0; i < n; i++) {
      if (!((col >> i) & 1) && !(D >> (q + n - 1 - i) & 1ULL) && !((D >> (q + i + 26)) & 1ULL)) {
          s[q] = i;
          c = col;
          tmp = D;
          col |= (1 << i);
          D |= (1ULL << (q + n - 1 - i)) | (1ULL << (q + i + 26));
          placeQueen(q + 1);
          col = c;
          D = tmp;
      }
    }
  }
}

int main(void) {
  f = fopen("damesah.in", "r");
  fscanf(f, "%d", &n);
  fclose(f);

  f = fopen("damesah.out", "w");
  placeQueen(0);
  fprintf(f, "%d\n", numSol);
  fclose(f);
  return 0;
}