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

int _count, _printed;
std::ofstream _out;
int _checkedLine[64], _checkedDiag[64];


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) {
		if (!_checkedLine[i] && !_checkedDiag[N+i-step] && !_checkedDiag[2*N+i+step]) {
			d[step] = i;
			
			_checkedLine[i] = 1;
			_checkedDiag[N+i-step] = 1;
			_checkedDiag[2*N+i+step] = 1;
			
			backtracking(d, step+1, N);
			
			_checkedLine[i] = 0;
			_checkedDiag[N+i-step] = 0;
			_checkedDiag[2*N+i+step] = 0;
		}	
	}
}

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;
}