#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>

using namespace std;

const string IN_FILE = "damesah.in";
const string OUT_FILE = "damesah.out";

inline int getDiagonal(const int n, const int r, const int c) {
    const int offset = (n - 1);
    return r - c + offset;
}

inline int getSecondaryDiagonal(const int n, const int r, const int c) {
    const int offset = (n - 1);
    return (n - 1 - r) - c + offset;
}

int back(
        const int n,
        vector<int>& queens,
        vector<bool>& columns,
        vector<bool>& diagonals,
        vector<bool>& secondaryDiagonals,
        vector<int>& first) {
    const int r = int(queens.size());
    if (r == n) {
        if (first.empty()) {
            first = queens;
        }
        return 1;
    }
    int count = 0;
    for (int c = 0; c < n; c++) {
        const int d = getDiagonal(n, r, c);
        const int sd = getSecondaryDiagonal(n, r, c);
        if (columns[c] || diagonals[d] || secondaryDiagonals[sd]) continue;
        queens.push_back(c);
        columns[c] = true;
        diagonals[d] = true;
        secondaryDiagonals[sd] = true;
        count += back(n, queens, columns, diagonals, secondaryDiagonals, first);
        queens.pop_back();
        columns[c] = false;
        diagonals[d] = false;
        secondaryDiagonals[sd] = false;
    }
    return count;
}

pair<vector<int>, int> solve(const int n) {
    vector<int> queens;
    auto columns = vector<bool>(n);
    auto diagonals = vector<bool>(2 * n - 1);
    auto secondaryDiagonals = vector<bool>(2 * n - 1);
    vector<int> first;
    const int count =
            back(n, queens, columns, diagonals, secondaryDiagonals, first);
    return make_pair(first, count);
}

int readInput() {
    ifstream in(IN_FILE);
    int n;
    in >> n;
    in.close();
    return n;
}

void writeOutput(const vector<int>& first, const int count) {
    ofstream out(OUT_FILE);
    for (int i = 0; i < int(first.size()); i++) {
        out << first[i] + 1 << (i + 1 < int(first.size()) ? " " : "\n");
    }
    out << count << "\n";
    out.close();
}

int main() {
    const int n = readInput();
    vector<int> first;
    int count;
    tie(first, count) = solve(n);
    writeOutput(first, count);
    return 0;
}