#include <fstream>
#include <iostream>

//std::ifstream in("Text.txt");

int st[14];
int nrSolutii = 0;
int first = 1;

bool bun(int pas)
{
	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++)
		std::cout << st[i] << " ";
	std::cout << 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;
	std::cin >> n;
	std::cin.ignore();

	bkt(1,n);
	std::cout << nrSolutii;
	std::cin.get();
}