#include <stdio.h>

#define maxn 15

int n;
int sol, x[maxn], solution[maxn], col[maxn], diag1[maxn<<1], diag2[maxn<<1];

void back(int niv) {

	if (niv == n+1) {
		if (!solution[1]) {
			for (int i = 1; i <= n; ++i) {
				solution[i] = x[i];
			}
		}
		++sol;
		return;
	}

	for (int i = 1; i <= n; ++i) {
		if (!col[i] && !diag1[n+niv-i] && !diag2[i+niv]) {
			col[i] = diag1[n+niv-i] = diag2[i+niv] = 1;
			x[niv] = i;
			back(niv+1);
			col[i] = diag1[n+niv-i] = diag2[i+niv] = 0;
		}
	}
}

int main() {

	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);

	scanf("%d", &n);

	back(1);

	for (int i = 1; i <= n; ++i) {
		printf("%d ", solution[i]);
	}
	printf("\n%d\n", sol);

	return 0;
}