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

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int count_solutions = 0;

void bt(int step, int n, vector<int>& sol, vector<bool>& col, vector<bool>& diag_princ, vector<bool>& diag_sec) {
	if (step == n + 1) {
		if(count_solutions < 1) {
			for (int i = 1; i <= n; i++) {
				fout << sol[i] << ' ';
			}
			fout << '\n';
		}
		count_solutions++;
	}

	for (int c = 1; c <= n; c++) {
		if (!col[c] && !diag_princ[step - c + n] && !diag_sec[step + c]) {
			col[c] = true;
			diag_princ[step - c + n] = true;
			diag_sec[step + c] = true;
			sol[step] = c;
			bt(step + 1, n, sol, col, diag_princ, diag_sec);
			col[c] = false;
			diag_princ[step - c + n] = false;
			diag_sec[step + c] = false;
		}
	}
}

int main() {
	int n;
	fin >> n;
	vector<int> sol(n + 1);
	vector<bool> col(n + 1);
	vector<bool> diag_princ(2 * n + 1);
	vector<bool> diag_sec(2 * n + 1);
	bt(1, n, sol, col, diag_princ, diag_sec);
	fout << count_solutions << '\n';
}