/*
Keep It Simple!
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include<stdio.h>
#define MaxN 19

int N,st[MaxN],sw,Pd[MaxN*2],c[MaxN],cnt,Sd[MaxN*2],viz[MaxN];

void PrintData(int k)
{
	for (int i = 1; i <= k; i++)
		printf("%d ", st[i]);
	printf("\n");
}


void back(int k)
{
	int i;
	for (i = 1; i <= N; i++)
	{
		if (!c[i] && !Pd[i - k + N] && !Sd[k + i])
		{
			st[k] = i;
			Pd[i - k + N] = 1;
			Sd[k + i] = 1;
			c[i] = 1;
			if (k == N)
				if (!cnt++)
					PrintData(k);
			if (k < N)
				back(k + 1);
			c[i] = 0;
			Pd[i - k + N] = 0;
			Sd[k + i] = 0;
		}
	}
}

int main()
{
	freopen("submultimi.in", "r", stdin);
	freopen("submultimi.out", "w", stdout);

	scanf("%d", &N);
		back(1);
	printf("%d", cnt);

	return 0;
}