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

void back(const int sz, vector<int>& v, int& i, vector<bool>& col, vector<bool>& diag_princ,
	vector<bool>& diag_sec, int& num_sol, ofstream& g){
	if(v.size() == sz){
		++num_sol;
		if(num_sol == 1){
			for(const auto x : v){
				g << (x+1) << ' '; }
			g << '\n'; } }
	else{
		for(int j = 0; j < sz; ++j){
			int pdp = j - i + sz,
				pds = j + i;
			if((!col[j]) && (!diag_princ[pdp]) && (
				!diag_sec[pds])){
				col[j] = true;
				diag_princ[pdp] = true;
				diag_sec[pds] = true;
				v.push_back(j);
				++i;
				back(sz, v, i, col, diag_princ, diag_sec, num_sol, g);
				--i;
				v.pop_back();
				col[j] = false;
				diag_princ[pdp] = false;
				diag_sec[pds] = false; } } } }

int main(){
	ifstream f("damesah.in");
	ofstream g("damesah.out");
	int n = 0;
	f >> n;
	vector<int> v;
	vector<bool> col(n, false), diag_princ(2*n, false), diag_sec(2*n, false);
	int num_sol=0, i = 0;
	back(n, v, i, col, diag_princ, diag_sec, num_sol, g);
	g << num_sol;
	return 0; }