#include <stdio.h>

#define N 13

int n;
int solutie[N];
int nrsol = 0;
int lex[N];
void bk(int k);
int check(int k);
int abs(int x) {
	return x < 0 ? x*-1 : x;
}

void bk(int k) {
	int i, p;

	for(i=0; i<n; i++) {
		solutie[k] = i;

		if(check(k)) {
			if(k+1 == n) {
				if(nrsol == 0) for(p=0; p<n; p++) lex[p] = solutie[p]+1;
				nrsol++;

			}

			else bk(k+1);
		}

	}

}

int check(int k) {
	for(int i = 0; i < k; i++) {
		if(abs(solutie[k]-solutie[i]) == k-i || solutie[i] == solutie[k]) {
			return 0;
		}
	}
	return 1;
}

int main() {
	int i;
	FILE *in, *out;

	in = fopen("damesah.in", "r");
	fscanf(in, "%d", &n);
	fclose(in);

	bk(0);

	out = fopen("damesah.out", "w");
	for(i=0; i<n; i++) fprintf(out, "%d ", lex[i]);

	fprintf(out, "\n%d", nrsol);

	fclose(out);


	return 0;
}