#include <fstream>

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

const int N = 13;

int st[10], k;
bool d1[2 * N], d2[2 * N], c[N];

static inline void afis(int n) {
  for (int i = 0; i < n; ++i)
    out << st[i] + 1 << ' ';
  out << '\n';
}

static inline bool valid(int i, int n) {
  if (c[i])
    return false;
  if (d1[k - i + n])
    return false;
  if (d2[k + i])
    return false;
  return true;
}

static inline void dame(int n) {
  int i = -1, dm = 0;
  bool am_afisat = false;
  while (k >= 0) {
    if (i < n - 1) {
      ++i;
      st[k] = i;
      if (valid(i, n)) {
        if (k == n - 1) {
          if (!am_afisat)
            afis(n);
          ++dm;
          am_afisat = true;
        }
        else {
          c[i] = true;
          d1[k - i + n] = true;
          d2[k + i] = true;
          i = -1;
          ++k;
        }
      }
    }
    else {
      --k;
      if (k >= 0) {
        i = st[k];
        c[i] = false;
        d1[k - i + n] = false;
        d2[k + i] = false;
      }
    }
  }
  out << dm << '\n';
}

int main() {
  int n;
  in >> n;
  dame(n);
  in.close();
  out.close();
  return 0;
}