#include <fstream>
#include <algorithm>

#define MaxN 15

using namespace std;

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

int N, v[MaxN], sol;

bool isValid(int k) {
	for (int i = 0; i < k; ++i)
		if (v[i] == v[k] || k - i == abs(v[k] - v[i]))
			return false;
	return true;
}

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

		if (isValid(k)) {
			if (k == N - 1) {
				if (sol == 0) {
					for (int j = 0; j < N; ++j) {
						fout << v[j] << ' ';
					}
					fout << '\n';
				}
				++sol;
			} else
				bk(k + 1);
		}
	}
}

int main() {
	fin >> N;

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