#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 20;

int tabla[MAXN][MAXN];
int n;
int numSol;
int solMax, solCurent;
int vSol[MAXN];
int atac[MAXN][MAXN];

void asezareDame(int i, int j, int alegere) {
    if (i == n + 1) {
        if (solCurent == solMax)
            ++numSol;
        if (solCurent > solMax) {
            solMax = solCurent;
            numSol = 1;
            for (int r = 1; r <= n; ++r)
                for (int c = 1; c <= n; ++c)
                    if (atac[r][c] == -1)
                        vSol[r] = c;
        }
        return;
    }

    if (j > n) return;

    if (atac[i][j] == 0) {
        atac[i][j] = -1;
        ++solCurent;
        for (int k = 1; k <= n; ++k) {
            if (atac[k][j] == 0) atac[k][j] = alegere;

            int c1 = j - i + k;
            if (c1 >= 1 && c1 <= n && atac[k][c1] == 0) atac[k][c1] = alegere;

            int c2 = i + j - k;
            if (c2 >= 1 && c2 <= n && atac[k][c2] == 0) atac[k][c2] = alegere;
        }

        asezareDame(i + 1, 1, alegere + 1);

        atac[i][j] = 0;
        --solCurent;
        for (int k = 1; k <= n; ++k) {
            if (atac[k][j] == alegere) atac[k][j] = 0;

            int c1 = j - i + k;
            if (c1 >= 1 && c1 <= n && atac[k][c1] == alegere) atac[k][c1] = 0;

            int c2 = i + j - k;
            if (c2 >= 1 && c2 <= n && atac[k][c2] == alegere) atac[k][c2] = 0;
        }
    }

    asezareDame(i, j + 1, alegere);
}

int main() {
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    cin >> n;
    asezareDame(1, 1, 1);
    for (int i = 1; i <= n; ++i)
        cout << vSol[i] << " ";
    cout << "\n" << numSol;
    return 0;
}