#include <iostream>
#include <fstream>
using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

int x[30], n, nr, ok;

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

void display_sol()
{
	for (int i = 1; i <= n; i++)
		g << x[i] << " ";
	g << "\n";
}

void dame(int k)
{
	for (x[k] = 1; x[k] <= n; x[k]++)
									 
		if (valid(k))
			if (k == n)
			{
				if (ok == 0)
				{
					display_sol();
					ok = 1;
				}
				nr++;
			}
			else
				dame(k + 1);
}

int main()
{
	f >> n;
	dame(1);
	g << nr;
	return 0;
}