/*
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");
}

bool valid(int k)
{
	if (viz[st[k]])
		return 0;
		if ( c[st[k]])
			return 0;
		if (Pd[st[k] - k + N] || Sd[k + st[k]])
			return 0;
		return 1;
}

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

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

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

	return 0;
}