#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <unordered_set>
using namespace std;

bool check(const vector<int>& v){
	unordered_set<int> diag_princ, diag_sec;
	for(int i = 0; i < v.size(); ++i){
		const bool a = (diag_princ.find(v[i]-i) == end(diag_princ)),
			b = (diag_sec.find(v[i]+i) == end(diag_sec));
		cout << i << ' ' << v[i] << ' ' << a << ' ' << b << '\n';
		if(!(a && b)){
			cout << endl;
			return false; }
		diag_princ.insert(v[i]-i);
		diag_sec.insert(v[i]+i); }
	cout << endl;
	return true; }

int main(){
	ifstream f("damesah.in");
	ofstream g("damesah.out");
	int n = 0;
	f >> n;
	vector<int> sol(n);
	int num_sol = 0;
	iota(begin(sol), end(sol), 0);
	do{
		if(check(sol)){
			++num_sol;
			if(num_sol == 1){
				for(const auto x : sol){
					g << (x+1) << ' '; }
				g << '\n'; } }
	} while(next_permutation(begin(sol), end(sol)));
	g << num_sol;
	return 0; }