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

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

#define DIM 20
int n, nr_sol;
int sol[DIM];
bool first = true;
bool column[DIM];
bool d1[DIM << 1];
bool d2[DIM << 2];


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;
			column[i] = true;
			d1[i - k + n] = true;
			d2[k + i] = true;
			Back(k + 1);
			d2[k + i] = false;
			d1[i - k + n] = false;
			column[i] = false;
			sol[k] = 0;
		}
};


bool Check(int k, int i)
{
	if (column[i] || d1[i - k + n] || d2[i + k])
		return false;
	
	return true;
};