#include <cstdio>
#include <vector>

using namespace std;

bool is_valid(int n, int x, int y, bool diags1[], bool diags2[], 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);

	bool columns[n+1];
	bool diags1[2*n+1];
	bool diags2[2*n+1];
	int used[n+1];
	int ys[n+1];

	for(int i=0; i<=n; ++i) {
        columns[i] = diags1[i] = diags2[i] = used[i] = ys[0] = 0;
	}

	for(int i=n+1; i<2*n+1 ;++i) {
        diags1[i] = diags2[i] = 0;
	}

	for(int i=1; i<=n; ++i)
	{
        diags1[n + 1 - i] = true;
        diags2[1 + i] = true;
        columns[i] = true;

        curr_step = 1;
        ys[1] = i;
        do {
            curr_y = ys[curr_step];

            if (curr_step == n) {
                if (solutionsno == 0) {
                    for(int j=1; 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) {
                diags1[n + curr_step - curr_y] = false;
                diags2[curr_step + curr_y] = false;
                columns[curr_y] = false;
                used[curr_step] = 0;
                --curr_step;
            } else {
                ++used[curr_step];
                if (is_valid(n, next_step, next_y, diags1, diags2, columns)) {
                    ys[next_step] = next_y;
                    diags1[n + next_step - next_y] = true;
                    diags2[next_step + next_y] = true;
                    columns[next_y] = true;
                    ++curr_step;
                }
            }

        } while (curr_step);

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

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