#include <bits/stdc++.h>

using namespace std;

int d1(int i, int j) { return i + j; }

int d2(int i, int j, int n) { return i - j + n - 1; }

void solve(int row, int n, vector<int>& col, vector<bool>& c, vector<bool>& d1v,
           vector<bool>& d2v, int& total, bool& printed) {
  if (row == n) {
    ++total;
    if (!printed) {
      printed = true;
      for (int x : col) cout << x + 1 << " ";
      cout << "\n";
    }
    return;
  }

  for (int j = 0; j < n; ++j) {
    int k1 = d1(row, j), k2 = d2(row, j, n);
    if (!c[j] && !d1v[k1] && !d2v[k2]) {
      c[j] = d1v[k1] = d2v[k2] = true;
      col[row] = j;
      solve(row + 1, n, col, c, d1v, d2v, total, printed);
      c[j] = d1v[k1] = d2v[k2] = false;
    }
  }
}

int main() {
#ifndef LOCAL
  freopen("damesah.in", "r", stdin);
  freopen("damesah.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  if (!(cin >> n)) return 1;
  vector<int> col(n);
  vector<bool> c(n), d1v(2 * n - 1), d2v(2 * n - 1);
  int total = 0;
  bool printed = false;
  solve(0, n, col, c, d1v, d2v, total, printed);
  cout << total << "\n";
}