#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 20
using namespace std;

FILE*IN,*OUT;

int N,Out[MaxN],Sol=0;
bool Col[MaxN],Diag1[MaxN],Diag2[MaxN],Shown=false;
void Back(int lvl)
{
	if(lvl==N+1)
	{
		Sol++;
		if(!Shown)
		{
			Shown=true;
			for(int i=1;i<=N;i++)
				fprintf(OUT,"%d ",Out[i]);
			fprintf(OUT,"\n");
		}
	}
	else
	{
		for(int i=1;i<=N;i++)
			if(!Col[i]&&!Diag1[lvl+i-1]&&!Diag2[N-lvl+i])
			{
				Out[lvl]=i;
				Col[i]=true,Diag1[lvl+i-1]=true,Diag2[N-lvl+i]=true;
				Back(lvl+1);
				Col[i]=false,Diag1[lvl+i-1]=false,Diag2[N-lvl+i]=false;
				Out[lvl]=0;
			}
	}
}

int main()
{
	IN=fopen("damesah.in","r");
	OUT=fopen("damesah.out","w");

	fscanf(IN,"%d",&N);
	Back(1);
	fprintf(OUT,"%d\n",Sol);
	return 0;
}