//#include <fstream>
//#include <cmath>
#include <stdio.h>
#include <math.h>

bool first = false;
int v[100];
int n;
int count = 0;
int firstsolution[100];

bool notAttacking(int k) {
	for(int i = 1; i < k; i++) {
		if(v[i] == v[k] || abs(i-k) == abs(v[i] - v[k])) return false;
	}
	return true;
}

void solve(int k) {
	for(int c = 1; c <= n; c++) {
		v[k] = c;
		if(notAttacking(k)) {
			if (k==n) {
				count++;
				if(!first) {
					first = true;
					for(int i = 1; i <= n; i++) {
						firstsolution[i] = v[i];
					}
				}			
			} else { solve (k+1); }
		}
	}
}

int main() {
	//std::ifstream fin("damesah.in");
	//std::ofstream fout("damesah.out");

	FILE *fin = fopen("damesah.in", "r");
	FILE *fout = fopen("damesah.out", "w");

	//fin >> n;
	
	fscanf(fin, "%d", &n);

	solve(1);

	for(int i = 1; i <= n; i++) {
	//	fout << firstsolution[i] << ' '; 
		fprintf(fout, "%d ", firstsolution[i]);
	}
	
	//fout << '\n';

	//fout << count << '\n';

	fprintf(fout, "\n%d\n", count);

}