#include<stdio.h>
#include<math.h>
#include<iostream>

int k, sol[20];

bool isValid(int k)
{
	for(int i = 1; i < k; ++i)
		if((sol[i] == sol[k]) || (k - i == abs(sol[k] - sol[i]))) 
			return false;
	return true;
}

int main()
{
	int N, nr_solutii = 0;
	bool valid, first = true;;

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

	scanf("%d", &N);

	k = 1;
	sol[k] = 0;

	while(k > 0)
	{
		valid = false;
		while((sol[k] < N) && (!valid))
		{
			sol[k]++;
			valid = isValid(k);
		}
		if(!valid)
			k--;
		else
		{
			if(k == N)
			{
				if(first)
				{
					for(int i = 1; i <= N; ++i)
						printf("%d ", sol[i]);
					first = false;
				}
				nr_solutii++;
			}
			else
			{
				k++;
				sol[k] = 0;
			}
		}
	}

	printf("\n");
	printf("%d\n", nr_solutii);
	return 0;
}