#include <iostream>
#include <fstream>
#include <vector>

int _count, _printed;
std::ofstream _out;

bool check(std::vector<int>& d, int step)
{
	for (int i = 0; i < step; ++ i) {
		if (d[i] == d[step]) {
			return false;
		}
		if (d[i] - d[step] == i - step) {
			return false;
		}
		if (d[i] - d[step] == step - i) {
			return false;
		}
	}
	return true;
}

void backtracking(std::vector<int>& d, int step, int N)
{
	if (step == N) {
		if (!_printed) {
			for (auto v : d) {
				_out << v << " ";
			}
			_out << "\n";
			_printed = 1;
		}
		++ _count;
		return;
	}
	
	for (int i = 1; i <= N; ++ i) {
		d[step] = i;
		if (!check(d, step)) {
			continue;
		}
		backtracking(d, step+1, N);
	}
}

int main() 
{
	std::ifstream in("damesah.in");
	
	int N;
	in >> N;
	std::vector<int> d(N);
	_out = std::ofstream("damesah.out");
	
	backtracking(d, 0, N);
	_out << _count << "\n";
	
	_out.close();
	in.close();
	return 0;
}