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

int sir[14],sir1[14],ok=1,n,total,diag1[27],diag2[27],linie[14];

void back (int poz)
{
	int i,j,k,okp=1;
	if (poz==n+1)
	{
		total++;
		if (ok) for (i=1; i<=n; i++) sir1[i]=sir[i];
		ok=0;
	}
	else
	{
		for (i=1; i<=n; i++)
		{ 
			if (!(linie[i] or diag1[poz+i-1] or diag2[n+i-poz]))
			{
				sir[poz]=i;
				linie[i]=diag1[poz+i-1]=diag2[n+i-poz]=1;
				back(poz+1);
				linie[i]=diag1[poz+i-1]=diag2[n+i-poz]=0;
			}
			else okp=1;
		}
	}
}

int main ()
{
	int i;
	FILE *f,*g;
	f=fopen("damesah.in", "r");
	g=fopen("damesah.out", "w");
	fscanf(f, "%d", &n);
	back (1);
	for (i=1; i<=n; i++) fprintf(g, "%d ", sir1[i]);
	fprintf(g, "\n");
	fprintf(g, "%d", total);
	fclose(f); fclose(g);
	return 0;
}