#include<stdio.h>
#include<math.h>

#define MAX 14
int N;
int sol[MAX],count;

int verifica(int i)
{
	for(int k=0;k<i;k++)
		if(sol[k]==sol[i] || abs(sol[k]-k)==abs(sol[i]-i))
			return 0;
	return 1;
}

void bt(int i,FILE* out)
{
	if(i==N)
	{
		if(!count)
			for(int k=0;k<N;k++)
				fprintf(out,"%d ",sol[k]);
		count++;
		return;
	}

	for(int p=1;p<=N;p++)
	{
		sol[i]=p;
		if(verifica(i))
			bt(i+1,out);
	}
}


int main()
{
	FILE* f,*g;
	f=fopen("damesah.in","r");
	g=fopen("damesah.out","w");
	fscanf(f,"%d",&N);
	bt(0,g);
	fprintf(g,"\n%d",count);
	return 0;
}