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

ifstream f("damesah.in");
ofstream g("damesah.out");
vector<int> v;
vector<bool> col, diag_princ, diag_sec;
int num_sol=0, i = 0, sz;

void back(){
	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();
				--i;
				v.pop_back();
				col[j] = false;
				diag_princ[pdp] = false;
				diag_sec[pds] = false; } } } }

int main(){
	f >> sz;
	col.resize(sz, false), diag_princ.resize(2*sz, false), diag_sec.resize(2*sz, false);
	v.reserve(sz);
	back();
	g << num_sol;
	return 0; }