#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int n;
int ok = 0;
int ans = 0;
int d1[30];
int d2[30];
int col[30];
int sol[30];


void BKT(int k)
{
	int r1, r2;
	if (k == n + 1)
	{
		ans++;
		if (ok == 0)
		{
			ok = 1;
			for (int i = 1; i <= n; i++)
			{
				g << sol[i] << " ";
			}
			g << "\n";
		}
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			r1 = k - i + n;
			r2 = k - (n + 1 - i) + n;
			if (d1[r1] == 0 and d2[r2] == 0 and col[i] == 0)
			{
				sol[k] = i;
				d1[r1] = 1;
				d2[r2] = 1;
				col[i] = 1;
				BKT(k + 1);
				d1[r1] = 0;
				d2[r2] = 0;
				col[i] = 0;
			}
		}

	}


}


int main()
{
	f >> n;
	BKT(1);
	g << ans;

}