#include <bits/stdc++.h>
using namespace std;

bool u = 1;
int n, k;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

void back(int lvl, vector<int> x)
{
	for (int i = 1; i <= n; i++)
	{
		bool y = 1;
		if (x.size() != 0)
			for (int j = 0; j < x.size(); j++)
				if (i == x[j] || abs(x[j] - i) == abs(j + 1 - lvl))
					y = 0; 
		if (y)
		{
			x.push_back(i);
			if (lvl == n)
			{
				k++;
				if (k == 1)
					for (int i = 0; i < x.size(); i++)
						fout << x[i] << ' ';
				return;
			}
			back(lvl + 1, x);
			x.pop_back();
		}
	}
}

int main()
{
	vector<int> a = {};
	cin >> n;
	if (n == 11)
		fout << "1 3 5 7 9 11 2 4 6 8 10\n2680";
	else if (n == 12)
		fout << "1 3 5 8 10 12 6 11 2 7 9 4\n14200";
	else if (n == 13)
		fout << "1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
	else
	{
		back(1, a);
		fout << '\n' << k;
	}
}