#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int col[N],dg[N],udg[N],g[N];
long long cnt,n;

void dfs(int u)
{
	if(u == n+1)
	{
		if(cnt < 3)
		{
			for(int i = 1;i <= n;i++) cout << g[i] << " ";
			cout << endl;
		}
		cnt++;
		return;
	}
	for(int i = 1;i <= n;i++)
	{
		if(!col[i] && !dg[u+i] && !udg[n-u+i])
		{
			g[u] = i;
			col[i] = dg[u+i] = udg[n-u+i] = true;
			dfs(u+1);
			col[i] = dg[u+i] = udg[n-u+i] = false;
		}
	}
	
}
int main()
{
	cin >> n;
	dfs(1);
	cout << cnt;
}