#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int N = 20;

int n, CountAns, ans[N];
bool Coloana[N], DiagPrin[2 * N], DiagSec[2 * N];

void PrintAns()
{
	CountAns++;
	if (CountAns == 1)
	{
		for (int i = 0; i < n; i++)
		{
			fout << ans[i] << ' ';
		}
		fout << '\n';
	}
}

bool CanPlace(int l, int c)
{
	return !DiagPrin[n + l - c] && !DiagSec[l + c] && !Coloana[c];
}

void MarkPlaced(int l, int c, bool placed)
{
	DiagPrin[n + l - c] = DiagSec[l + c] = Coloana[c] = placed;
}

void bkt(int level)
{
	if (level == n)
	{
		PrintAns();
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (CanPlace(level, i))
		{
			ans[level] = i;
			MarkPlaced(level, i, true);
			bkt(level + 1);
			MarkPlaced(level, i, false);
		}
	}
}

int main()
{
	fin >> n;
	bkt(0);
	fout << CountAns;
}