#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
struct solutii {
	int x, y;
};

int n;

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

void afisare_rezultat(solutii *v) {
	for (int i = 0; i < n; i++)
		fout << v[i].y+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, solutii *v) {
	v[x].x = x;
	v[x].y = 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 *diag_1, int *diag_2, int *coloane,solutii *v,int &first_time,int &counter) {
	if (solutie(k)) {
		if (first_time) {
			afisare_rezultat(v);
			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, v);
			back_track(k + 1, diag_1, diag_2, coloane,v,first_time,counter);
			coloane[i] = 0;
			scoatere_diag(k, i, diag_1, diag_2);
		}

}


int main()
{
	int diag_1[10], diag_2[10], coloane[10],first_time=true,counter=0;
	solutii v[10];
	fin >> n;
	back_track(0, diag_1, diag_2, coloane, v,first_time,counter);
	fout << counter;
	return 0;

}