#include<fstream>
#include<map>
using namespace std;
map<pair<int, int>, int> diag1, diag2;
ifstream cin("damesah.in");
ofstream cout("damesah.out");
int n, sol[12], rep[12], m, frecv1[100], frecv2[100], cntf;
bool border(int a, int b) {
	if (a >= 1 && a <= n && b >= 1 && b <= n) {
		return true;
	}
	else {
		return false;
	}
}
void backtracking(int poz) {
	if (poz == n + 1) {
		cntf++;
		if (cntf == 1) {
			for (int i = 1; i <= n; i++) {
				cout << sol[i] << ' ';
			}
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (rep[i] == 0) {
				rep[i] = 1;
				int inter = i, debug1 = diag1[{poz, inter}], debug2 = diag2[{poz, inter}];
				if (frecv1[diag1[{poz, inter}]] == 0 && frecv2[diag2[{poz, inter}]] == 0) {
					sol[poz] = i;
					frecv1[diag1[{poz, inter}]] = 1;
					frecv2[diag2[{poz, inter}]] = 1;
					backtracking(poz + 1);
					frecv1[diag1[{poz, inter}]] = 0;
					frecv2[diag2[{poz, inter}]] = 0;
				}
				rep[i] = 0;
			}
		}
	}
}
int main() {
	cin >> n;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		cnt++;
		int x = i;
		int y = 1;
		while (border(x, y) == 1) {
			diag1[{x, y}] = cnt;
			y++;
			x++;
		}
	}
	for (int i = 2; i <= n; i++) {
		cnt++;
		int x = 1;
		int y = i;
		while (border(x, y) == 1) {
			diag1[{x, y}] = cnt;
			y++;
			x++;
		}
	}
	cnt = 0;
	for (int i = n; i >= 1; i--) {
		cnt++;
		int x = 1;
		int y = i;
		while (border(x, y) == 1) {
			diag2[{x, y}] = cnt;
			y--;
			x++;
		}
	}
	for (int i = 2; i <= n; i++) {
		cnt++;
		int x = i;
		int y = n;
		while (border(x, y) == 1) {
			diag2[{x, y}] = cnt;
			y--;
			x++;
		}
	}
	backtracking(1);
	cout << '\n' << cntf;
}