#include<fstream>
using namespace std;

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

int contor = 0;
bool varwrite = 1;

int perm[50];
int col[50];
int diag1[100];
int diag2[100];

void back(int poz, int n)
{
	if(poz == n+1)
	{
		contor++;
		if(varwrite == 1)
		{
			varwrite = 0;
			for(int i = 1; i <= n; i++)
			{
				fout << perm[i] << " ";
			}
		}
		return;
	}

	for(int i = 1; i <= n; i++)
	{
		if(!col[i] && !diag1[i-poz+n] && !diag2[i+poz])
		{
			col[i] = 1;
			diag1[i-poz+n] = 1;
			diag2[i+poz] = 1;
			perm[poz] = i;
			back(poz+1, n);
			diag2[i+poz] = 0;
			diag1[i-poz+n] = 0;
			col[i] = 0;
		}
	}
}

int main()
{
	int n;
	fin >> n;
	back(1,n);
	fout << "\n" << contor;
	fin.close();
	fout.close();
}