#include <iostream>
#include <fstream>

using namespace std;

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

int n, x[21], nr;
bool col[21], diag1[21], diag2[21];

bool Valid(int i, int k) {
	return !(col[i] || diag1[n + k - i] || diag2[i + k]);
}

void Back(int k) {
	if (k == n + 1) {
		if (!nr)
			for (int i = 1; i <= n; i++)
				fout << x[i] << " ";
		nr++;
	}
	else {
		for (int i = 1; i <= n; i++)
			if (Valid(i, k)) {
				x[k] = i;
				col[i] = 1, diag1[n + k - i] = 1, diag2[i + k] = 1;
				Back(k + 1);
				col[i] = 0, diag1[n + k - i] = 0, diag2[i + k] = 0;
			}
	}
}

int main() {
	fin >> n;
	Back(1);
	fout << "\n" << nr;
	return 0;
}