#include <fstream>
#include <iostream>
#include <cstdio>

using namespace std;

//ofstream out("damesah.out");
FILE *in, *out;
bool matrix[14][14];
short cols[14];
short decided_pos[14];
bool wrote = false;
int nr_sol = 0;
int max_linii;

void print_matrix()
{

	return;

	for (int i = 0; i < max_linii; i++)
	{
		for (int j = 0; j < max_linii; j++)
			cout << matrix[i][j] << " ";

		cout << endl;
	}

	cout << endl;
}

void modify_spaces(bool added, int linie, int col)
{
	for (int i = linie; i < max_linii; i++)
	{
		matrix[i][col] = added;
	}

	int i = linie, j = col;

	while (i < max_linii && j < max_linii)
	{
		matrix[i][j] = added;
		i++, j++;
	}

	i = linie, j = col;

	while (i < max_linii && j >= 0)
	{
		matrix[i][j] = added;
		i++, j--;
	}

}

void bkt(int linie)
{
	if (linie >= max_linii)
	{
		if (nr_sol == 0)
		{
			for (int i = 0; i < max_linii; i++)
			{
				//out << decided_pos[i] + 1 << " ";
				fprintf(out, "%d ", decided_pos[i] + 1);
			}
			//out << endl;
			fprintf(out, "\n");
		}

		nr_sol++;

		return;
	}

	for (int col = 0; col < max_linii; col++)
	{

		if (matrix[linie][col] == 0)
		{
			modify_spaces(true, linie, col);
			decided_pos[linie] = col;
			bkt(linie + 1);
			modify_spaces(false, linie, col);
		}
	}

}

int main()
{
	//ifstream in("damesah.in");
	//in >> max_linii;

	in = fopen("damesah.in", "r");
	out = fopen("damesah.out", "w");
	fscanf(in, "%d", &max_linii);

	bkt(0);

	//out << nr_sol << endl;
	fprintf(out, "%d\n", nr_sol);

	return 0;
}