#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, x[16], check[16], diag1[32], diag2[32], nrsol;

inline bool cond(int k)
{
	if(check[x[k]]) return 0;
	if(diag1[n + k - x[k]]) return 0;
	if(diag2[k + x[k]]) return 0;
	return 1;
}

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

int main()
{
	f>>n;
	back_dame(1);
	g<<'\n'<<nrsol;
	g.close();
	return 0;
}