#include <iostream>
#include <fstream>
#include <bitset>
#include <cstring>

#define NMAX 14
const char IN[] = "damesah.in", OUT[] = "damesah.out";

using namespace std;

int N;
ifstream fin(IN);

bitset<NMAX*2> takeCol, takeMainDiag, takeSecDiag;
bool first = true;

int sol;

int perm[NMAX];
int firstSol[NMAX];

void bkt(int k, int i) {
	if (k == N + 1) {
		++sol;
		if (first) {
			first &= 0;
			memcpy(firstSol, perm, sizeof(perm));
		}
		return;
	}
	for (int j = 1; j <= N; ++j) {
			if (takeCol[j] || takeMainDiag[j-i+N] || takeSecDiag[i+j]) continue;
			perm[k] = j;
			takeCol[j].flip();
			takeMainDiag[j - i + N].flip();
			takeSecDiag[i + j].flip();
			bkt(k + 1, i + 1);			
			takeMainDiag[j - i + N].flip();
			takeSecDiag[i + j].flip();
			takeCol[j].flip();
		}		
}

int main() {
	fin >> N;
	bkt(1,1);
	freopen(OUT, "w", stdout);
	for (int i = 1; i <= N; ++i) {
		printf("%d ", firstSol[i]);
	}
	printf("\n%d\n", sol);
	fclose(stdout);
	return 0;
}