#include <fstream>

std::fstream fin("damesah.in", std::ios::in);
std::fstream fout("damesah.out", std::ios::out);

int n, sol[15], ans;
bool messi = false;

void afis() {
  for (int i = 1; i <= n; ++i) {
    fout << sol[i] << ' ';
  }
  fout << '\n';
}

bool verif(int k) {
  for (int i = 1; i < k; ++i) {
    if ((sol[i] == sol[k]) || abs(sol[k] - sol[i]) == (k - i)) return false;
  }
  return true;
}

void bkt(int k) {
  for (int i = 1; i <= n; ++i) {
    sol[k] = i;

    if (verif(k)) {
      if (k == n) {
        ans++;
        if (messi == false) {
          messi = true;
          afis();
        }
      }

      bkt(k + 1);
    }
  }
}

int main() {
  fin >> n;
  bkt(1);
  fout << ans;
  return 0;
}