#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int N, P[30], Sol;
bool Col[30], LDiag[30], RDiag[30];

void gen(int K) {
	int R, L;
	if (K > N) {
		Sol++;
		if (Sol == 1) {
			for (int i = 1; i <= N; i++) printf("%d ", P[i]);
			printf("\n");
		}
	}
	for (int i = 1; i <= N; i++) {
		R = K + i - 1;
		L = K + (N - i + 1) - 1;
		if (!Col[i] && !RDiag[R] && !LDiag[L]) {
			P[K] = i;
			Col[i] = RDiag[R] = LDiag[L] = 1;
			gen(K + 1);
			Col[i] = RDiag[R] = LDiag[L] = 0;
		}
	}
}

int main() {
	
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
	
	scanf("%d", &N);
	gen(1);
	printf("%d\n", Sol);
	
	return 0;
}