#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, v[14], nr;
bool ok,
     fr[14];
bool verif(int k)
{
	for(int i = 1; i < k; i++)
	{
		if(abs(v[k] - v[i]) == k - i)
			return 0;
	}
	return 1;
}
void afis()
{
	for(int i = 1; i <= n; i++)
		g << v[i] << ' ';
}
void bt(int k)
{
	if(k <= n)
	{
		for(int i = 1; i <= n; i++)
		{
			if(!fr[i])
			{
				fr[i] = 1;
				v[k] = i;
				if(verif(k))
					bt(k + 1);
				fr[i] = 0;
			}
		}
	}
	else
	{
		if(ok == 0)
			afis();
        ok=1;
		nr++;
	}
}
int main()
{
	f >> n;
	bt(1);
	g<<'\n'<<nr;
	f.close();
	g.close();
	return 0;
}