#include <cstdio>

int pos[2 + 13], sol = 0;

bool diagP[2 + 30], diagS[2 + 30], freq[2 + 13];

inline void findPos(int n, int step) {
  if (step > n) {
    if (sol == 0) {
      for (int i = 1; i <= n; i++)
        printf("%d ", pos[i]);
      printf("\n");
    }
    sol++;
  } else
    for (int i = 1; i <= n; i++)
      if (!freq[i] && !diagP[step + n - 1 - i] && !diagS[step + i]) {
        diagP[step + n - 1 - i] = true;
        diagS[step + i] = true;
        freq[i] = true;
        pos[step] = i;
        findPos(n, step + 1);
        diagP[step + n - 1 - i] = false;
        diagS[step + i] = false;
        freq[i] = false;
      }
}
int main() {
  freopen("damesah.in", "r", stdin);
  freopen("damesah.out", "w", stdout);
  int n;
  scanf("%d", &n);
  findPos(n, 1);
  printf("%d", sol);
  return 0;
}