#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 15;

int solCurenta[MAXN];
int sol[MAXN];
bool col[MAXN];
bool diag1[2 * MAXN];
bool diag2[2 * MAXN];
int n, numSol;

void asezareDame(int rand) {
    if (rand == n + 1) {
        ++numSol;
        if (numSol == 1) {
            for (int i = 1; i <= n; ++i)
                sol[i] = solCurenta[i];
        }
        return;
    }
    for (int coloana = 1; coloana <= n; ++coloana) {
        if (!col[coloana] && !diag1[rand - coloana + n] && !diag2[rand + coloana]) {
            col[coloana] = true;
            diag1[rand - coloana + n] = true;
            diag2[rand + coloana] = true;
            solCurenta[rand] = coloana;
            asezareDame(rand + 1);
            col[coloana] = false;
            diag1[rand - coloana + n] = false;
            diag2[rand + coloana] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    cin >> n;

    asezareDame(1);

    for (int i = 1; i <= n; ++i)
        cout << sol[i] << " ";
    cout << "\n" << numSol;

    return 0;
}