#include <fstream>
#define IN "damesah.in"
#define OUT "damesah.out"
#define NMAX 15

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int n, sol[NMAX], contor;
bool viz[NMAX], principal[2*NMAX], secundar[2*NMAX], sw=1;

inline void BT(int k)
{
	for(int i=1; i<=n; ++i)
	{
		if(viz[i] || principal[n-k+i] || secundar[k+i-1])
			continue;
		sol[k]=i;
		viz[i]=principal[n-k+i]=secundar[k+i-1]=1;
		if(k==n)
			++contor;
		if(sw && k==n)
		{
			for(int j=1; j<=n; ++j)
				out<<sol[j]<<' ';
			out<<'\n';
			sw=0;
		}
		else
			BT(k+1);
		viz[i]=principal[n-k+i]=secundar[k+i-1]=0;
	}
}

int main()
{
	in>>n;
	BT(1);
	out<<contor<<'\n';
	in.close();
	out.close();
	return 0;
}