#include<cstdio>
#include<cmath>
#define NMAX 15
using namespace std;

int S[NMAX], dame[NMAX], sol, N;
bool main_diag[NMAX<<1], sec_diag[NMAX<<1], col[NMAX];


bool valid(int i, int k) {

	/*
	for (int j = 1 ; j < k ; j++) 
		if ((k - j) == abs(S[j] - i) || S[j] == i)
			return false;
	return true;
	*/
	return !main_diag[k-i+N] && !sec_diag[k+i-1] && !col[i];
}

void back(int k) {

    for (int i = 1 ; i <= N ; i++) {
        if (!valid(i, k)) continue;
		
		S[k] = i;

		main_diag[k - i + N] = true;
		sec_diag[k + i - 1] = true;
		col[i] = true;
         
		if (k == N) {
            sol++;
			if (sol == 1) 
				for (int j = 1 ; j <= N ; j++)
					dame[j] = S[j];
            
			main_diag[k - i + N] = false;
			sec_diag[k + i - 1] = false;
			col[i] = false; 
		}
		else {
			back(k+1);
			main_diag[k - i + N] = false;
			sec_diag[k + i - 1] = false;
			col[i] = false; 
		}
	}
}

int main() {

    freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);

	scanf("%d", &N);
	back(1);
	
	for (int i = 1 ; i <= N ; i++)
		printf("%d ", dame[i]);
	printf("\n%d\n", sol);

	return 0;
}