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

int S[NMAX], dame[NMAX], sol, N;

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;
}

void back(int k) {

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

		}
		else back(k+1);
	}
}

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;
}