#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

void backtracking(int linie, int n, vector<int>& sol, vector<int>& primaSol,
                  vector<bool>& coloana, vector<bool>& diag1, vector<bool>& diag2,
                  long long& total, bool& primaGasita)
{
    if (linie > n) {
        total++;

        if (!primaGasita) {
            primaGasita = true;
            primaSol = sol;
        }
        return;
    }

    for (int col = 1; col <= n; col++) {
        int d1 = linie - col + n;
        int d2 = linie + col;

        if (!coloana[col] && !diag1[d1] && !diag2[d2]) {

            sol[linie] = col;

            coloana[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;

            backtracking(linie + 1, n, sol, primaSol, coloana,
                         diag1, diag2, total, primaGasita);

            coloana[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }
}

int main() {

    int n;
    fin >> n;

    vector<int> sol(n + 1);
    vector<int> primaSol(n + 1);

    vector<bool> coloana(n + 1, false);

    vector<bool> diag1(2 * n + 1, false);
    vector<bool> diag2(2 * n + 1, false);

    long long total = 0;

    bool primaGasita = false;

    backtracking(1, n, sol, primaSol, coloana,
                 diag1, diag2, total, primaGasita);

    for (int i = 1; i <= n; i++) {
        fout << primaSol[i] << " ";
    }

    fout << '\n';
    fout << total;

    return 0;
}