#include <fstream>
#include <cmath>

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");

	fin >> n;

	solve(1);

	for(int i = 1; i <= n; i++) {
		fout << firstsolution[i] << ' '; 
	}
	
	fout << '\n';

	fout << count << '\n';

}