#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, k = 1, x[14], check[14], nrsol;

bool cond()
{
	for(int i = 1; i < k; ++i)
		if(x[i] == x[k] || abs(x[k] - x[i]) == abs(k-i)) return 0;
	return 1;
}

void back_dame()
{
	k++;
	for(int i = 1; i <= n; ++i)
	{
		if(check[i]) continue;
		x[k] = i;
		if(k == 1 || cond())
		{
			check[i] = 1;
			if(k == n)
			{
				if(!nrsol) for(int i = 1; i <= n; ++i) g<<x[i]<<' ';
				nrsol++;
			}
			else back_dame();
			check[i] = 0;
		}
	}
	k--;
}

int main()
{
    f>>n;
    for(int i = 1; i <= n; ++i)
	{
		x[k] = i;
		check[i] = 1;
		back_dame();
		check[i] = 0;
	}
    g<<'\n'<<nrsol;
    return 0;
}