#include <bits/stdc++.h>
#ifdef BLAT
   #include "debug/debug.hpp"
#else
   #define debug(x...)
#endif

using namespace std;

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

void back(int x, vector <bool> &col, vector <bool> &diag_p, 
        vector <bool> &diag_s, vector <int> &sol, int &nrsol) {
    int n = col.size();

    if (sol.size() == n) {
        nrsol++;
        if (nrsol == 1) {
            for (int i : sol)
                out << i + 1 << ' ';
            out << '\n';
        }

        return;
    }

    for (int i = 0; i < n; i++) {
        // ba, io vreau sa pun dama pe linia x si coloana i
        if (col[i] == false && diag_p[n + i - x - 1] == false && diag_s[x + i] == false) {
            sol.push_back(i);
            col[i] = diag_p[n + i - x - 1] = diag_s[x + i] = true;

            back(x + 1, col, diag_p, diag_s, sol, nrsol);

            // backtrack
            col[i] = diag_p[n + i - x - 1] = diag_s[x + i] = false;
            sol.pop_back();
        }
    }
}

int main() {
    int n;
    vector <bool> col, diag_p, diag_s;
    vector <int> sol;
    int nrsol = 0;

    in >> n;
    col.resize(n);
    diag_p.resize(2 * n - 1);
    diag_s.resize(2 * n - 1);

    back(0, col, diag_p, diag_s, sol, nrsol);
    out << nrsol << '\n';
    return 0;
}