#include<stdio.h>
FILE *in, *out;
int N, S[15], count;
bool found = false;
void open()
{
	in = fopen("damesah.in", "rt");
	out = fopen("damesah.out", "wt");
}
void read()
{
	fscanf(in, "%d", &N);
}
void writefound()
{
	for (int i = 1; i <= N; i++)
		fprintf(out, "%d ", S[i]);
}
bool inbounds(int x, int y)
{
	return (x >= 1 && x <= N && y >= 1 && y <= N);
}
bool equalpositions(int firstx, int firsty, int secondx, int secondy)
{
	return (firstx == secondx && firsty == secondy);
}
bool attackingQueens(int firstx, int firsty, int secondx, int secondy)
{
	if ((firstx == secondx) || (firsty == secondy)) return true;

	for (int i = firstx, j = firsty; inbounds(i, j); i++, j++)
		if (equalpositions(i, j, secondx, secondy)) return true;

	for (int i = firstx, j = firsty; inbounds(i, j); i--, j--)
		if (equalpositions(i, j, secondx, secondy)) return true;

	for (int i = firstx, j = firsty; inbounds(i, j); i--, j++)
		if (equalpositions(i, j, secondx, secondy)) return true;

	for (int i = firstx, j = firsty; inbounds(i, j); i++, j--)
		if (equalpositions(i, j, secondx, secondy)) return true;

	return false;
}
bool isvalidqueen(int x, int y, int current)
{
	for (int i = 1; i < current; i++)
		if (attackingQueens(x, y, i, S[i]))
			return false;
	return true;
}
void bkt(int current)
{
	if (current == N + 1)
	{
		count++;
		if (!found)
		{
			found = true;
			writefound();
		}
	}
	for (int i = 1; i <= N; i++)
		if (isvalidqueen(current, i, current))
		{
			S[current] = i;
			bkt(current + 1);
		}
}
int main()
{
	open();
	read();
	bkt(1);

	fprintf(out, "\n%d", count);
	return 0;
}