#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int v[13], n, k, isoke, rez[13];
bool whoke(int k)
{
	for (int i = 1; i < k; i++)
		if ((v[k] == v[i]) || (k - i == abs(v[k] - v[i])))
			return false;
	return true;
}
void update(int n)
{
	for (int i = 1; i <= n; i++)
		rez[i] = v[i];
}
int bak(int n)
{
	int isoke, k, r = 0;
	bool first = 1;
	k = 1, v[k] = 0;
	while (k > 0)
        {
		isoke = 0;
		while ((v[k] < n) && (!isoke)) ++v[k], isoke = whoke(k);
		if (!isoke) k--;
		else
			if (k == n)
                        {
				if (first) update(n), first = 0;
				r++;
			}
			else
				v[++k] = 0;
	}
	return r;
}

int main()
{
        ios::sync_with_stdio(false);
        fin.tie(0);

	fin >> n;
	int ans = bak(n);
	for (int i = 1; i <= n; i++)
		fout << rez[i] << " ";
	fout << "\n" << ans;

	return 0;
}