#include <fstream>
#include <vector>

class Chess_queen {
public:
    Chess_queen(int k);

    void generate(int k);

    int getNumofSol();

    std::vector<int> getFirstSolVec();

private:
    bool foundsol;
    std::vector<int> sol;
    std::vector<int> colpos;
    std::vector<int> row, main_diag, anti_diag;
    int n, solnum;
};

Chess_queen::Chess_queen(int k) : n(k) {
    row.resize(n);
    main_diag.resize(2 * n - 1);
    anti_diag.resize(2 * n - 1);
    colpos.resize(n);
    foundsol = 0;
    solnum = 0;
}

void Chess_queen::generate(int k) {
    for (int i = 0; i < n; i++) {
        if (row[i] == 0 && main_diag[i + k] == 0 && anti_diag[i - k + n] == 0) {
            main_diag[i + k] = 1;
            anti_diag[i - k + n] = 1;
            row[i] = 1;

            colpos[k] = i;
            if (k != n - 1) generate(k + 1);
            else {
                solnum++;
                if (!foundsol) {
                    sol = colpos;
                    foundsol = 1;
                }
            }
            main_diag[i + k] = 0;
            anti_diag[i - k + n] = 0;
            row[i] = 0;
        }
    }
}

int Chess_queen::getNumofSol() {
    return solnum;
}

std::vector<int> Chess_queen::getFirstSolVec() {
    return sol;
}


int main() {
    std::ifstream fin("damesah.in");
    int n;
    fin >> n;
    fin.close();

    Chess_queen chq(n);
    chq.generate(0);

    std::ofstream fout("damesah.out");
    std::vector<int> sol = chq.getFirstSolVec();
    for (int e:sol) fout << e + 1 << " ";
    fout << "\n" << chq.getNumofSol();
}