#include <iostream>
using namespace std;
const int N = 20;

int n, ans = 0, a1[N], a2[N], a3[N], b[N];

void dfs(int x)
{
	if(x > n)
	{
		ans ++;
		if(ans <= 3)
		{
			for(int i = 1;i <= n;i ++)
			{
				cout << b[i] << ' ';
			}
			cout << endl;
		}
		return;
	}
	
	for(int i = 1;i <= n;i ++)
	{
		if(a1[i] == 0 && a2[x + i] == 0 && a3[x - i + 15] == 0)
		{
			b[x] = i;
			a1[i] = 1;
			a2[x + i] = 1;
			a3[x - i + 15] = 1;
			dfs(x + 1);
			a1[i] = 0;
			a2[x + i] = 0;
			a3[x - i + 15] = 0;
		}
	}
}

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

QAQ为什么为什么为什么