#include <fstream>

using namespace std;
const int NMAX = 13;
int N, x[NMAX + 1], nrSol;
bool C[NMAX + 1], dP[2 * NMAX], dS[2 * NMAX];
ifstream f("damesah.in");
ofstream g("damesah.out");
void afis()
{
	for(int i = 1; i <= N; i++)
		g << x[i] << ' ';
	g << '\n';
}
void BT(int k)
{
	if(k <= N)
	{
		for(int i = 1; i <= N; i++)
		{
			if(C[i] == 0 && dP[N - k + i] == 0 && dS[k + i - 1] == 0)
			{
				x[k] = i;
				C[i] = dP[N - k + i] = dS[k + i - 1] = 1;
				BT(k + 1);
				C[i] = dP[N - k + i] = dS[k + i - 1] = 0;
			}
		}
	}
	else
	{
		if(nrSol == 0)
			afis();
		nrSol++;
	}
}
int main()
{
	f >> N;
	BT(1);
	g << nrSol;
	f.close();
	g.close();
	return 0;
}