#include <iostream>
using namespace std;
int n,cnt = 0;
int h1[20] = {0},x1[40] = {0},x2[40] = {0};
void dep(int dp,int l)
{
	if(dp == n+1)
	{
		cnt++;
		for(int i=1;i<=n;i++)
		{
			cout<<h1[i]<<" ";
		}
		cout<<endl;
		return;
	}
	if(l <= 0||l > n)
		return;
	
	for(int h=1;h<=n;h++)
	{
		if(h1[h] == 0&&!x1[l+h]&&!x2[n + l - h])
		{
			h1[h] = l;
			x1[l+h] = 1;
			x2[n + l - h] = 1;
			dep(dp+1,l+1);
			h1[h] = 0;
			x1[l+h] = 0;
			x2[n + l - h] = 0;
		}
	}
}
int main()
{
	cin>>n;
	dep(1,1);
	cout<<cnt;
	return 0;
}