#include <bits/stdc++.h>
using namespace std;

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

  int n;
  fin >> n;

  int solutions = 0;
  vector<int> buf(n, 0);
  vector<bool> used(n, false), diag1(2 * n - 1, false), diag2(2 * n - 1, false);

  auto back = [&](auto &&back, int current = 0) {
    if (current == n && solutions++ == 0) {
      for (int i = 0; i < n; ++i)
        fout << buf[i] + 1 << ' ';
      fout << '\n';
      return;
    }

    for (int i = 0; i < n; ++i) {
      buf[current] = i;

      if (!used[buf[current]] && !diag1[buf[current] - current + n - 1] &&
          !diag2[buf[current] + current]) {
        used[buf[current]] = true;
        diag1[buf[current] - current + n - 1] = true;
        diag2[buf[current] + current] = true;

        back(back, current + 1);

        used[buf[current]] = false;
        diag1[buf[current] - current + n - 1] = false;
        diag2[buf[current] + current] = false;
      }
    }
  };

  back(back);

  fout << solutions << '\n';
}