#include <iostream>
#include <fstream>

std::ofstream out("damesah.out");

const int NMAX = 13;

int n;

int solutions = 0;
bool found_first = false;

int sol[1 + NMAX];

bool col[1 + NMAX];

bool diff_diag[1 + NMAX + NMAX];

bool sum_diag[1 + NMAX + NMAX];

void read() {
  std::ifstream in("damesah.in");

  in >> n;

  in.close();
}

void found_solution() {
  if (!found_first) {
    for (int i = 1; i <= n; ++i)
      out << sol[i] << ' ';
    out << '\n';
    found_first = true;
  }
  ++solutions;
}

void backtrack(int depth) {
  for (int i = 1; i <= n; ++i) {
    if (!col[i] && !diff_diag[n + depth - i] && !sum_diag[depth + i]) {
      sol[depth] = i;

      if (depth == n)
        found_solution();
      else {
        col[i] = true;
        diff_diag[n + depth - i] = true;
        sum_diag[depth + i] = true;

        backtrack(depth + 1);

        col[i] = false;
        diff_diag[n + depth - i] = false;
        sum_diag[depth + i] = false;
      }
    }
  }
}


int main() {
  read();

  backtrack(1);

  out << solutions << '\n';

  out.close();
  return 0;
}