#include <fstream>

using namespace std;

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

const int MAXN = 13;
int sol[MAXN + 1];
int cnt, n;

int abs(int nr) {
	return max(nr, -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 = 1;
			for (int j = 1; j < k && ok; ++ j) {
				if (sol[j] == i) ok = false;
				if (abs(sol[j] - i) == abs(j - k)) ok = false;
			}

			if (ok) {
				sol[k] = i;
				bck(k + 1);
			}
		}
	}
}

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