#include <cstdio>
#include <bitset>
#define DM 15
using namespace std;

FILE * fi;
FILE * fo;
int t[DM][DM], n, v[DM], c, pos = 1;
bool verif;
bitset <DM> col;
bitset <DM> di1;
bitset <DM> di2;

void bkt (int a)
{
	if (a == n + 1)
	{
		++c;
		if (!verif)
			for (int i = 1; i <= n; ++i)
			{
				fprintf (fo, "%d ", v[i]);
				verif = 1;
			}
		return;
	}
	for (int i = 1; i <= n; ++i)
	{
		if (!col[i] && !di1[a-i+n] && !di2[i+a])
		{
			col[i] = 1, di2[i+a] = 1, di1[a-i+n] = 1, v[pos] = i; 
			++pos;
			bkt (a + 1);
			col[i] = 0, di2[i+a] = 0, di1[a-i+n] = 0, v[pos] = 0;
			--pos;
		}
	}
}

int main ()
{
	fi = fopen ("damesah.in", "r");
	fo = fopen ("damesah.out", "w");
	fscanf (fi, "%d", &n);
	bkt(1);
	fprintf (fo, "\n%d", c);
	return 0;
}