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

FILE *in,*out;

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


//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)
			{
				if(!prop)
				{	
					for(int i=1; i<=n; ++i)
						fprintf(out,"%d ",answer[i]);
					fprintf(out,"\n");
				}
				if(!prop)
					prop=true;
				ras++;
			}	
			else
				back(k+1);
	}	
}
bool valid(int k)
{
	for(int i=1; i<k; ++i)
	{
		if(answer[k]==answer[i] || abs(answer[i]-answer[k])==abs(i-k))
			return false;
	}	
	return true;
	
}