#include <fstream>
using namespace std;

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

int Check(int i, int j);
void Back(int i);
void Read();
void Write();

const int dim = 50;
int n, S[dim], rez, col[dim], dp[dim], ds[dim];

int main()
{
	Read();
	Back(1);
	fout << rez;
	
	fout.close();
}

int Check(int i, int j)
{
	if (col[j] || ds[i + j] || dp[i - j + n])
		return 0;
	return 1;
}

void Back(int i)
{
	if (i == n + 1)
		Write();
	else
	{
		for (int j = 1; j <= n; j++)
			if ( Check(i, j) )
			{
				col[j]++;
				ds[i + j]++;
				dp[i - j + n]++;
				S[i] = j;
				Back(i + 1);
				col[j]--;
				ds[i + j]--;
				dp[i - j + n]--;
				S[i] = 0;
			}
	}
}

void Read()
{
	fin >> n;
	fin.close();
}

void Write()
{
	if ( !rez )
	{
		for (int i = 1; i <= n; i++)
			fout << S[i] << ' ';
		fout << '\n';
		rez++;
	}
	else
		rez++;
}