#include <fstream>
#include <algorithm>

#define MaxN 15

using namespace std;

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

int N, v[MaxN], sol, diag_princ[2*MaxN], diag_sec[2*MaxN], col[MaxN];

void bk(int k) {
	for (int i = 1; i <= N; ++i) {
		v[k] = i;

		if (!col[i] && !diag_princ[k + i - 1] && !diag_sec[N - i + k]) {
			if (k == N) {
				if (sol == 0) {
					for (int j = 1; j <= N; ++j) {
						fout << v[j] << ' ';
					}
					fout << '\n';
				}
				++sol;
			} else {
				col[i] = diag_princ[k + i - 1] = diag_sec[N - i + k] = 1;
				bk(k + 1);
				col[i] = diag_princ[k + i - 1] = diag_sec[N - i + k] = 0;
			}
		}
	}
}

int main() {
	fin >> N;

	bk(1);
	fout << sol << '\n';
	
	return 0;
}