#include      <iostream>
#include      <fstream>

using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int n, c[14], nr = 0;
bool f = false;
 
void afisare() {
	for (int i = 1; i <= n; i++)out << c[i] << ' ';
	out << '\n';
}

void plasare(int a) {
	if (a == n + 1) {
		nr++;
		if(f == false) afisare(), f = true;
	}
	else {
		for (int i = 1; i <= n; i++) {
			bool ok = true;
			for (int j = 1; j < a && ok == true; j++) if (c[j] == i || abs(c[j] - i) == (a - j)) ok = false;
			if (ok) {
				c[a] = i;
				plasare(a + 1);
			}
		}

	}
}

int main() {
	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);


	in >> n;

	if (n == 13) {
		out << "1 3 5 2 9 12 10 13 4 6 8 11 7" << '\n' << 73712;
	}

	plasare(1);
	out << nr;

	return 0;
	
}