#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20;
int g[N][N];
int n;
int path[N];
int col[N], updg[N], lowdg[N];
int cnt=0;

void dfs(int u)
{
	if (u > n)
	{
		cnt ++;
		if (cnt <= 3)
		{
			for (int i=1; i <= n; i ++)	//输出方案！
				cout << path[i] << " ";
			puts(""); 
		}
		return ;
	}
	
	for (int i=1; i <= n; i ++)	//循环枚举的是列！ 
	{
		if (!col[i] && !updg[u+i] && !lowdg[n-u+i] && g[u][i]==0)
		{
			col[i] = updg[u+i] = lowdg[n-u+i] = true;
			g[u][i] = 1;
			path[u] = i;
			
			dfs(u+1);
			
			g[u][i] = 0;
			col[i] = updg[u+i] = lowdg[n-u+i] = false;
			path[u] = 0;
		}
	}
}

int main()
{
	cin >> n;
	dfs(1);
	cout << cnt;
	return 0;
}