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

int N, sol[NMAX], firstSol[NMAX], countSolutions;
bool takenColumn[NMAX], takenFirstDiagonal[LMAX], takenSecondDiagonal[LMAX];

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 (!takenColumn[col] && !takenFirstDiagonal[idx - col + NMAX] && !takenSecondDiagonal[idx + col]) {
			sol[idx] = col;
			takenColumn[col] = true;
			takenFirstDiagonal[idx - col + NMAX] = true;
			takenSecondDiagonal[idx + col] = true;

			createSol(idx + 1);
			takenColumn[col] = false;
			takenFirstDiagonal[idx - col + NMAX] = false;
			takenSecondDiagonal[idx + col] = false;
		}
	}
}

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;
}