#include<stdio.h>
#include<stdlib.h>

FILE *in,*out;

//functii
void back(int k);
bool valid(int k);
int tipar();

//constante 
const int Nmax=14;

//variabile
int n;
int answer[Nmax],ras;
bool prop=false;

int main(void)
{
	in=fopen("damesah.in","rt");
	out=fopen("damesah.out","wt");
	fscanf(in,"%d",&n);
	answer[0]=-1;
	back(1);
	
	fprintf(out,"%d",ras);
	
	fclose(in);
	fclose(out);
	return 0;
	
}	
void back(int k)
{
	for(int i=1; i<=n; ++i)
	{
		answer[k]=i;
		if(valid(k))
			if(k==n)
				tipar();
			else
				back(k+1);
	}	
}
bool valid(int k)
{
	if(answer[k]==answer[k-1]+1 || answer[k]+1==answer[k-1])
		return false;
	for(int i=1; i<k; ++i)
	{
		if(answer[k]==answer[i] || abs(answer[i]-answer[k])==abs(i-k))
			return false;
	}	
	return true;
	
}	
int tipar()
{ 
	if(!prop)
	{	
		for(int i=1; i<=n; ++i)
			fprintf(out,"%d ",answer[i]);
		fprintf(out,"\n");
	}
	if(!prop)
		prop=true;
	ras++;
}