#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int diag_1[13], diag_2[13], coloane[13], n,v[13];

bool solutie(int k) {
	if (k == n) return true;
	else return false;
}

void afisare_rezultat() {
	for (int i = 0; i < n; i++)
		fout << v[i]+1 << " ";
}

void punere_diag(int x, int y, int *diag_1, int *diag_2) {
	if (y - x >= 0) diag_1[y - x] = 1;
	else diag_1[n + x - y - 1] = 1;
	diag_2[x + y] = 1;
}

void scoatere_diag(int x, int y, int *diag_1, int *diag_2) {
	if (y - x >= 0) diag_1[y - x] = 0;
	else diag_1[n + x - y - 1] = 0;
	diag_2[x + y] = 0;
}

void adaugare_solutii(int x,int y) {
	v[x] = y;
}

bool continuare(int x, int y, int *diag_1, int *diag_2, int *coloane) {
	if (coloane[y] == 1) return false;
	if (y - x >= 0 && (diag_1[y - x] == 1 || diag_2[x + y] == 1)) return false;
	if (y - x <0 && (diag_1[n + x - y - 1] == 1 || diag_2[x + y] == 1)) return false;
	return true;
}

void back_track(int k, int &first_time, int &counter) {
	if (solutie(k)) {
		if (first_time) {
			afisare_rezultat();
			first_time = false;
			fout << endl;
		}
		counter++;
	}
	for (int i = 0; i<n; i++)
		if (continuare(k, i, diag_1, diag_2, coloane)) {
			coloane[i] = 1;
			punere_diag(k, i, diag_1, diag_2);
			adaugare_solutii(k,i);
			back_track(k + 1,first_time, counter);
			coloane[i] = 0;
			scoatere_diag(k, i, diag_1, diag_2);
		}

}


int main()
{
	int first_time = true, counter = 0;
	fin >> n;
	back_track(0,first_time, counter);
	fout << counter << endl;
	return 0;

}