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

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n, nr_sol;
int sol[20];
bool first = true;
bool line[20];
bool column[20];

void Back(int k);
bool Check(int k, int i);

int main()
{
	fin >> n;
	Back(1);

	fout << nr_sol;
}


void Back(int k)
{
	if (k > n)
	{
		if (first)
		{
			first = false;
			for (int i = 1; i <= n; ++i)
				fout << sol[i] << ' ';
			fout << '\n';
		}
		nr_sol++;
		return;
	}

	for (int i = 1; i <= n; ++i)
		if (Check(k, i))
		{
			sol[k] = i;
			line[k] = true, column[i] = true;
			Back(k + 1);
			line[k] = false, column[i] = false;
			sol[k] = 0;
		}
};


bool Check(int k, int i)
{
	if (line[k] || column[i])
		return false;

	for (int j = 1; j <= k; ++j)
		if (abs(j - k) == abs(sol[j] - i))
			return false;
	return true;
};