P1219

#include <bits/stdc++.h>
using namespace std;
int a[16][16];
int l[16];
int n,ans;

void paint(int x,int y)
{
	int x1=x+1,y1=y-1;
	while (x1<=n && y1>0)
	{
		a[x1][y1]++;
		x1++; y1--;
	}
	x1=x+1; y1=y+1;
	while (x1<=n && y1<=n)
	{
		a[x1][y1]++;
		x1++; y1++; 
	}
	x1=x+1; y1=y;
	
	while (x1<=n)
	{
		a[x1][y1]++;
		x1++;
	}
	
}



void depaint(int x,int y)
{
	int x1=x+1,y1=y-1;
	while (x1<=n && y1>0)
	{
		a[x1][y1]--;
		x1++; y1--;
	}
	x1=x+1; y1=y+1;
	while (x1<=n && y1<=n)
	{
		a[x1][y1]--;
		x1++; y1++; 
	}
	x1=x+1; y1=y;
	
	while (x1<=n)
	{
		a[x1][y1]--;
		x1++;
	}
}


void dfs(int x,int y)
{
	if (x==n) {
	ans++;
	if (ans<=3)
	{
		for (int i=1;i<=n;i++) cout<<l[i]<<" ";
		cout<<endl;
	}
	}
else {
	for (int i=1;i<=n;i++)
	    if (a[x+1][i]==0){
	    	l[x+1]=i;
	    	paint (x+1,i);
	    	dfs(x+1,i);
	    	depaint(x+1,i);
	    	l[x+1]=0;
	    	}
}
} 
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		l[1]=i;
		paint(1,i);
		dfs(1,i);
		depaint(1,i);
		l[1]=0;
	}
	cout<<ans;
}