#include <cstdio>
#include <vector>

using namespace std;

bool is_valid(int n, int x, int y, vector<bool> &diags1, vector<bool> &diags2, vector<bool> &columns)
{
	if (columns[y] == true || diags1[n + x-y] == true || diags2[x+y] == true)
        return false;
	return true;
}


void backt(int n, int curr_step, int &solutionsno, vector<int> & ys, vector<int> & sols,
           vector<bool> &diags1, vector<bool> &diags2, vector<bool> &columns)
{
	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(n, curr_step, i, diags1, diags2, columns)) {
            diags1[n + curr_step - i] = true;
            diags2[curr_step + i] = true;
            columns[i] = true;

			ys.push_back(i);
			backt(n, curr_step + 1, solutionsno, ys, sols, diags1, diags2, columns);
			ys.pop_back();

            diags1[n + curr_step - i] = false;
            diags2[curr_step + i] = false;
            columns[i] = false;
		}
}



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

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

	vector<bool> columns(n+1);
	vector<bool> diags1(2*n);
	vector<bool> diags2(2*n);
	vector<int> solutions;
	vector<int> ys;
	ys.push_back(0);

	backt(n, 1, solutionsno, ys, solutions, diags1, diags2, columns);

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

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