#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, sol[14], nrsol;


int elem(int k)
{
	int i;
	for (i = 1; i<k; i++)
	{
		if (sol[i] == sol[k] || sol[k]==sol[k-1] || sol[k]==sol[k-2])
			return 0;
		for (i = 1; i < k; i++)
			if ((k - i) == abs(sol[k] - sol[i]))
				return 0;
		return 1;
	}

}

int solutie(int k)
{
	if (k == n)
		return 1;
	return 0;

}

int dupli()
{
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (sol[i] == sol[j])
				return 1;
	return 0;
}

void tiparire(int k)
{
	if (!dupli())
	{
		nrsol++;
		if (nrsol == 1)
		{
			for (int i = 1; i <= n; i++)
				g << sol[i] << " ";
			g << "\n";
		}
	}
}

void BackTracking(int k)
{
	int i,p=0;
	for (i =1; i <= n; i++)
	{
		sol[k] = i;
		if (elem(k))
		{
			if (solutie(k))
			{
				tiparire(k);
			}
			else
				BackTracking(k + 1);
		}

	}
}



int main()
{
	f >> n;
	BackTracking(1);
	g << nrsol;
	return 0;
}