#include<iostream>
#include<cstring>
using namespace std;
int n, a[100], b[100], c[100], d[100];
int ans = 0;
void dfs(int x)
{
	if (x > n)
	{
		ans++;
		if (ans <= 3)
		{
			for (int i = 1; i <= n; i++)
			{
				cout << a[i] << ' ';
			}
			cout << endl;
		}
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (b[x] == 0 && c[x + i] == 0 && d[x-i+n] == 0)
		{
			a[x] = i;
			b[x] = 1, c[x + i] = 1, d[i- x +n] = 1;
			dfs(x + 1);
			b[x] = 0, c[x + i] = 0, d[i - x + n] = 0;
		}
	}
}
int main()
{
	cin >> n;
	dfs(1);
	cout << ans;
	return 0;
}