#include <cstdio>
#include <cmath>

using namespace std;

int x[13], solutie[13];

void WriteData (int n)
{
	for (int i = 1; i <= n; ++i)
		solutie[i] = x[i];
}

bool eValid (int k)
{
	for (int i = 1; i < k; ++i)
	{
		double val = x[k] - x[i];
		if ((x[i] == x[k]) || (k - i == abs(val)))
			return false;
	}
	return true;
}

int Back (int n)
{
	int k;
	k = 1;
	x[k] = 0;
	int ksol = 0;
	bool first = true, eSol;
	while (k > 0)
	{
		eSol = false;
		while ((x[k] < n) && (!eSol))
		{
			x[k]++;
			eSol = eValid (k);
		}
		if (!eSol)
			--k;
		else
		{
			if (k == n)
			{
				if (first)
				{
					WriteData (n);
					first = false;
				}
				++ksol;
			}
			else
			{
				++k;
				x[k] = 0;
			}
		}
	}
	return ksol;
}

int main ()
{
	freopen ("damesah.in", "r", stdin);
	freopen ("damesah.out", "w", stdout);
	int n;
	scanf ("%d", &n);
	int ksol = Back (n);
	for (int i = 1; i <= n; ++i)
		printf ("%d ", solutie[i]);
	printf ("\n");
	printf ("%d", ksol);
	return 0;
}