#include <fstream>
#define SIZE 14
using namespace std;

#define ABS(x) ((x) < 0 ? -(x) : (x))

bool C[SIZE], PD[SIZE*2], SD[SIZE*2];
int n, s, Q[SIZE];


ifstream ifs("damesah.in");
ofstream ofs("damesah.out");

	
void backtrack(int q)
{
	if (q > n)
	{
		++s;
		
		if (s == 1)
		{
			// Print first solution
			for (int i = 1; i <= n; ++i)
			{
				ofs << Q[i] << " ";
			}
			
			ofs << "\n";
		}
	} 
	else
	{
		for (int j = 1; j <= n; ++j)
		{
			if (!C[j] && !PD[n-q+j] && !SD[q+j])
			{
				Q[q] = j;
				
				C[j] = PD[n-q+j] = SD[q+j] = true;
				backtrack(q+1);
				C[j] = PD[n-q+j] = SD[q+j] = false;
			}
		}
	}
}


int main()
{	
	ifs >> n;
	backtrack(1);
	ofs << s;
	
	return 0;
}