#include <stdio.h>

#define abs(x) ((x) > 0 ? (x) : (-(x)))

#define NMAX 15

int main() {
	int n, k = 1, st[NMAX], i, cnt = 0;
	bool as, ev;
	FILE *in = fopen("damesah.in", "r"), *out = fopen("damesah.out", "w");
	fscanf(in, "%d", &n);
	while (k) {
		do {
			as = 0;
			if(st[k] < n) {
				++st[k];
				as = 1;
			}
			if(as) {
				ev = 1;
				for(i = 1; i < k; ++i)
					if(k - i == abs(st[k] - st[i]) || st[i] == st[k])
						ev = 0;
			}
		} while(as && !ev);
		if(as)
			if(k == n) {
				if(cnt == 0)
					for(i = 1; i <= n; ++i)
						fprintf(out, "%d ", st[i]);
				++cnt;
		 	} else
				st[++k] = 0;
		else
			--k;
	}
	fprintf(out, "\n%d\n", cnt);
	fclose(in);
	fclose(out);
}