#include<stdio.h>

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

int myabs(int x)
{
	if(x<0)
		return -x;
	return x;
}

int verifica(int i)
{
	for(int k=0;k<i;k++)
		if(sol[k]==sol[i] || myabs(i-k)==myabs(sol[i]-sol[k]))
			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]+1);
		count++;
		return;
	}

	for(int p=0;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;
}