#include <stdio.h>
#define NMAX 35

int n, cnt;
int lin[NMAX], col[NMAX], d1[NMAX], d2[NMAX];

int sol[NMAX];

void bkt(int k) {

	if (k == n + 1) {

		if (!cnt)
			for (int i = 1; i <= n; ++i)
				sol[i] = lin[i];
		++cnt;
		return;
	}

	for (register int i = 1; i <= n; ++i)
		if (!col[i] && !d1[n + k - i] && !d2[i + k]) {

			col[i] = 1;
			lin[k] = i;
			d1[n + k - i] = 1;
			d2[i + k] = 1;

			bkt(k + 1);

			col[i] = 0;
			lin[k] = 0;
			d1[n + k - i] = 0;
			d2[i + k] = 0;
		}
}

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

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

	bkt(1);

	out = fopen("damesah.out", "wt");
	for (int i = 1; i <= n; ++i)
		fprintf(out, "%d ", sol[i]);

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

	fclose(out);
	return 0;
}