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

int sir[14],sir1[14],ok,n,total;

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=1;
	}
	else
	{
		for (i=1; i<=n; i++)
		{ 
			for (j=1; j<poz and okp; j++)
				if (i==sir[j]) okp=0;
			for (j=poz-1,k=1; j>=1 and okp and i-k>=1; j--,k++)
				if (i-k==sir[j]) okp=0;
			for (j=poz-1,k=1; j>=1 and okp and i+k<=n; j--,k++)
				if (i+k==sir[j]) okp=0;
			//cout<<poz<<" "<<i<<" "<<okp<<"\n";
			if (okp)
			{
				sir[poz]=i;
				back(poz+1);
			}
			else okp=1;
		}
	}
}

int main ()
{
	int i;
	FILE *f,*g;
	f=fopen("damesah.in", "r");
	g=fopen("damesah.out", "w");
	fscanf(f, "%d", &n);
	sir[0]=14;
	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;
}