#include <cstdio>
#include <vector>

using namespace std;

bool is_valid(int x, int y, vector<int> &ys)
{
	for(int i=1; i<ys.size(); ++i) {
		if (y == ys[i] || x - y == i - ys[i] || x + y == i + ys[i])
			return false;
	}
	return true;
}


void backt(int n, int curr_step, int &solutionsno, vector<int> & ys, vector<int> & sols)
{
	if (curr_step == n+1) {
		if(sols.size() == 0)
			sols.assign(ys.begin(), ys.end());
		++solutionsno;
		return;
	}

	for (int i=1; i<=n; ++i)
		if (is_valid(curr_step, i, ys)) {
			ys.push_back(i);
			backt(n, curr_step + 1, solutionsno, ys, sols);
			ys.pop_back();
		}
}



int main() {
	freopen("damesah.in", "r", stdin);
	freopen("damesah.out", "w", stdout);

	int n, solutionsno = 0;
	scanf("%d", &n);

	vector<int> solutions;
	vector<int> ys;
	ys.push_back(0);

	backt(n, 1, solutionsno, ys, solutions);

	for(int i=1; i<solutions.size(); ++i) {
		printf("%d ", solutions[i]);
	}

	printf("\n%d\n", solutionsno);
	return 0;
}