#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

int n, ok = 0, nr_solutii = 0;
vector<vector<char>> tabla;
vector<int> pozitii;

bool e_liber(int linie, int col) {
	// de jos in sus pe coloana
	for (int i = 0; i < linie; i++) {
		if (tabla[i][col] == 'D') return false;
	}
	int i = linie - 1;
	int j = col - 1;

	// stanga sus
	while (i >= 0 && j >= 0) {
		if (tabla[i][j] == 'D') return false;
		i--;
		j--;
	}

	// dreapta sus
	i = linie - 1;
	j = col + 1;
	while (i >= 0 && j < n) {
		if (tabla[i][j] == 'D') return false;
		i--;
		j++;
	}
	return true;
}

void backtrack(int k, ofstream& fout) {
	if (k == n && ok == 0) {
		ok = 1;
		for (int i = 0; i < n; i++) {
			fout << pozitii[i] << " ";
		}
		fout << endl;

		nr_solutii++;
		return;
	} else if (k == n && ok == 1) {
		nr_solutii++;
		return;
	}

	for (int j = 0; j < n; j++) {
		if (e_liber(k, j)) {
			tabla[k][j] = 'D';
			pozitii.push_back(j + 1);

			backtrack(k + 1, fout);

			tabla[k][j] = '_';
			pozitii.pop_back();
		}
	}
}

int main() {
	ifstream fin("damesah.in");
	ofstream fout("damesah.out");
	
	fin >> n;
	tabla.resize(n, vector<char>(n, '_'));
	backtrack(0, fout);

	fout << nr_solutii << endl;

	fin.close();
	fout.close();

	return 0;
}