#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define max(a,b) a > b ? a : b
#define ll long long int
namespace cv
{
	int size;
}

using namespace std;
ifstream f("damesah.in");
ofstream o("damesah.out");
int cate;
int tabla[15][15];
vector<int>ans(200);
bool col[20], dpUsed[200], dsUsed[200];
int nrsol;


void markPlaced(int row, int column, bool value)
{
	int dp = row - column + cv::size;
	int ds = row + column;
	dpUsed[dp] = value;
	dsUsed[ds] = value;
	col[column] = value;

}

bool eok(int row, int column)
{
	int dp = row - column + cv::size;
	int ds = row + column;
	if (dpUsed[dp] == false && dsUsed[ds] == false && col[column] == false)
	{
		return true;
	}
	return false;
}

void afisare()
{
	nrsol++;

	if (nrsol == 1)
	{
		for (int i = 0; i < cv::size; i++)
		{
			o << ans[i] + 1 << " ";
		}
		o << "\n";
	}
}

void bkt(int row)
{
	if (row == cv::size)
	{
		afisare();
	}
	else
	{
		for (size_t i = 0; i < cv::size; i++)
		{
			ans.push_back(i);
			if (eok(row, i))
			{
				ans[row] = i;
				markPlaced(row, i, true);
				bkt(row + 1);
				markPlaced(row, i, false);
			}
		}
	}
}

int main()
{
	f >> cv::size;
	bkt(0);
	o << nrsol;
}