#include <fstream>
#include <iostream>
 
std::ifstream in("damesah.in");
std::ofstream out("damesah.out");
 
int st[14];
int nrSolutii = 0;
int first = 1;
 
bool bun(int pas)
{
	if(pas > 1)
		if (st[pas - 1] == st[pas] || 1 == abs(st[pas] - st[pas - 1]))
			return false;
	for (int i = 1; i < pas; i++)
	{
		if (st[i] == st[pas] || (pas - i) == abs(st[pas] - st[i]))
			return false;
	}
	return true;
}
 
void Print(int n)
{
	for (int i = 1; i <= n; i++)
		out << st[i] << " ";
	out << std::endl;
}
 
void bkt(int pas, int n)
{	
	for (int i = 1; i <= n; i++)
	{
		st[pas] = i;
		if (bun(pas))
		{
			if (pas == n)
			{
				if (first)
				{
					Print(n);
					first = 0;
					nrSolutii++;
				}
				else
				{
					nrSolutii++;
				}
			}
			else
				bkt(pas + 1, n);
 
		}
	}
}
 
int main()
{
	int n;
	in >> n;
	
 
	bkt(1,n);
	out << nrSolutii;
}