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

using namespace std;

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

class Solver {
  public:
    Solver(const int _n) :
            n(_n),
            queens(new int[_n]),
            columns(new bool[_n]),
            diagonals(new bool[2 * n - 1]),
            secondaryDiagonals(new bool[2 * n - 1]),
            first(vector<int>()),
            count(0) {
        memset(columns, 0, sizeof(bool) * n);
        memset(diagonals, 0, sizeof(bool) * (2 * n - 1));
        memset(secondaryDiagonals, 0, sizeof(bool) * (2 * n - 1));
    }

    pair<vector<int>, int> solve() {
        if (first.empty()) {
            back(0);
        }
        return make_pair(first, count);
    }

    ~Solver() {
        delete[] queens;
        delete[] columns;
        delete[] diagonals;
        delete[] secondaryDiagonals;
    }

  private:
    int n;
    int* queens;
    bool* columns;
    bool* diagonals;
    bool* secondaryDiagonals;
    vector<int> first;
    int count;

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

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) = Solver(n).solve();
    writeOutput(first, count);
    return 0;
}