#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int N = 128;

bool column[N], diag_l[N], diag_r[N];
int pos[N], g[N];

int ans, n;

void bkt(int l) {
    if (l == n + 1) {
        if (!ans)
            for (int i = 1; i <= n; ++i)
                g[i] = pos[i];

        ans+= 1;
        return; }

    for (int c = 1; c <= n; ++c) {
        if (!column[c] && !diag_l[l + c] && !diag_r[l - c + n]) {
            column[c] = diag_l[l + c] = diag_r[l - c + n] = 1;
            pos[l] = c;

            bkt(l + 1);

            column[c] = diag_l[l + c] = diag_r[l - c + n] = 0; } } }

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

    scanf("%d", &n);

    bkt(1);
    for (int i = 1; i <= n; ++i)
        printf("%d ", g[i]);
    printf("\n%d\n", ans);

    return 0; }