#include <cstdio>
#include <cstring>
const int NMAX = 15;

int N, sol[NMAX], firstSol[NMAX], countSolutions;

inline bool freeDiagonal(int line, int col) {
	for (int l = 1; l < line; l++) {
		// first diagonal
		if (l - sol[l] == line - col) {
			return false;
		}
		// second diagonal
		if (l + sol[l] == line + col) {
			return false;
		}
	}

	return true;
}

inline bool freeColumn(int line, int col) {
	for (int l = 1; l < line; l++) {
		if (sol[l] == col) {
			return false;
		}
	}

	return true;
}

void createSol(int idx) {
	if (idx == N + 1) {
		countSolutions++;
		if (countSolutions == 1) {
			memcpy(firstSol, sol, sizeof(sol));
		}
		return ;
	}

	for (int col = 1; col <= N; col++) {
		if (freeColumn(idx, col) && freeDiagonal(idx, col)) {
			sol[idx] = col;
			createSol(idx + 1);
		}
	}
}

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

	scanf("%d", &N);
	createSol(1);

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

	return 0;
}