#include<iostream>
using namespace std;
int n,ans=0;
bool col[15],x1[30],x2[30],y[15];
bool check(int i,int j)
{
	return !col[j]&&!x1[i+j]&&!x2[i-j+n];
}
void dfs(int r)
{
	if(r==n)
	{
		ans++;
		if(ans<=3)
		for(int i=0;i<n;i++)
		{
			cout<<y[i];
			if(i!=n-1)cout<<" ";
			else cout<<endl;
		}
		return;
	}
	for(int i=0;i<n;i++)
	{
		if(check(r,i)){
		y[r]=i+1;
		x1[r+i]=x2[r-i+n]=col[i]=true;
		dfs(r+1);
		x1[r+i]=x2[r-i+n]=col[i]=false;
		}
		
	}
}
int main()
{
	cin>>n;
	dfs(0);
	cout<<ans;
	return 0;
}