#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 (y <= n && columns[y] == true || diags1[n + x-y] == true || diags2[x+y] == true)
        return false;
	return true;
}


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

	int n, solutionsno = 0, curr_step, curr_y, next_step, next_y;
	scanf("%d", &n);

	vector<bool> columns(n+1);
	vector<bool> diags1(2*n);
	vector<bool> diags2(2*n);
	vector<int> used(n+1, 0);
	vector<int> ys;

	for(int i=1; i<=n; ++i)
	{
        ys.push_back(i);
        diags1[n + 1 - i] = true;
        diags2[1 + i] = true;
        columns[i] = true;
        do {
            curr_step = ys.size();
            curr_y = ys[ys.size() - 1];

            if (curr_step == n) {
                if (solutionsno == 0) {
                    for(int j=0; j<n; ++j) {
                        printf("%d ", ys[j]);
                    }
                }
                ++solutionsno;
            }

            next_step = curr_step + 1;
            next_y = used[curr_step] + 1;

            if (next_y == n+1 || curr_step == n) {
                ys.pop_back();
                diags1[n + curr_step - curr_y] = false;
                diags2[curr_step + curr_y] = false;
                columns[curr_y] = false;
                used[curr_step] = 0;
            } else {
                if (is_valid(n, next_step, next_y, diags1, diags2, columns)) {
                    ys.push_back(next_y);
                    diags1[n + next_step - next_y] = true;
                    diags2[next_step + next_y] = true;
                    columns[next_y] = true;
                }
                ++used[curr_step];
            }

        } while (ys.size());

        used[1] = 0;
        diags1[n + 1 - i] = false;
        diags2[1 + i] = false;
        columns[i] = false;
	}

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