#include <fstream>

using namespace std;

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

const int MAXN = 13;
int sol[MAXN + 1];
int cnt, n;
bool lin[MAXN + 1], diag1[MAXN * 2 + 1], diag2[MAXN * 2 + 1];

int abs(int nr) {
	if (nr < 0)
		return -nr;
	return nr;
}

int bck(int k) {
	if (k > n) {
		++ cnt;
		if (cnt == 1) {
			for (int i = 1; i <= n; ++ i) out << sol[i] << ' ';
			out << '\n';
		}
	}
	else {
		for (int i = 1; i <= n; ++ i) {
			bool ok = true;
			if (lin[i]) ok = false;
			if (diag1[k - i + n]) ok = false;
			if (diag2[k + i]) ok = false;

			if (ok) {
				sol[k] = i;
				lin[i] = true;
				diag1[k - i + n] = true;
				diag2[k + i] = true;
				bck(k + 1);
				lin[i] = false;
				diag1[k - i + n] = false;
				diag2[k + i] = false;
			}
		}
	}
}

int main() {
	in >> n;
	bck(1);
	out << cnt;
	return 0;
}