/*
	Keep It Simple!
*/

#include<fstream>

using namespace std;

int Queens[20], N;
bool Coloana[20], Diag1[20], Diag2[20];
int cnt;
ifstream f("damesah.in");
ofstream g("damesah.out");


bool valid(int k)
{
	if (Coloana[Queens[k]] == 1)
		return 0;
	if (Diag1[Queens[k]-k+N-1] == 1)
		return 0;
	if (Diag2[k + Queens[k]] == 1)
		return 0;

	return 1;
}

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

		if (valid(k))
		{
			Coloana[i] = 1;
			Diag1[i - k + N - 1] = 1;
			Diag2[k+i] = 1;

			if (k == N)
			{
				if (!cnt)
				{
				for (int i = 1; i <= k; i++) 
					g << Queens[i] << ' ';
				g << '\n';
				}
				cnt++;
			}
			else if (k < N)
				Back(k + 1);

			Coloana[i] = 0;
			Diag1[i - k + N - 1] = 0;
			Diag2[k + i] = 0;
		}
	}
}

int main()
{

	f >> N;
	Back(1);
	g << cnt;

	f.close();
	g.close();
	return 0;
}