#include <cstdio>
#define nmax 40
using namespace std;

bool lin[nmax],diag1[nmax],diag2[nmax];
int sah[nmax],best[nmax];
int n,nr;

void gen(int p) {
	if (p>n) {
		if (!best[1]) for (int j=1;j<=n;j++) best[j] = sah[j];
		nr++;
	}
	for (int i=1;i<=n;i++) {
		if (!lin[i] && !diag1[p-i+100] && !diag2[i+p+100]) {
				lin[i] = diag1[p-i+100] = diag2[i+p+100] = true;
				sah[p] = i;
				gen(p+1);
				sah[p] = 0;
				lin[i] = diag1[p-i+100] = diag2[i+p+100] = false;
		}
	}
}

int main() {
	freopen("damesah.in","r",stdin);
	freopen("damesah.out","w",stdout);
	scanf("%d",&n);
	gen(1);
	for (int i=1;i<=n;i++) printf("%d ",best[i]);
	printf("\n%d\n",nr);
	return 0;
}