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

using namespace std;

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

int sol = 0, n;
bool first = true;
vector <bool> row(13, true), col(13, true), diag1(2 * 13 - 1, true), diag2(2 * 13 - 1, true);
vector <int> coords(13, 0);

void place_dama(int dim, int last_i) {
    if (dim == n) {
        sol++;
        if (first) {
            for (int i = 0; i < n; i++)
                out << coords[i] + 1 << ' ';
            out << '\n';
            first = false;
        }
        return;
    }
    for (int i = last_i + 1; i < n; i++) {
        if (!row[i])
            continue;
        for (int j = 0; j < n; j++) {
            if (!col[j] || !diag1[j - i + n - 1] || !diag2[j + i])
                continue;
            coords[i] = j;
            row[i] = false;
            col[j] = false;
            diag1[j - i + n - 1] = false;
            diag2[j + i] = false;
            place_dama(dim + 1, i);
            row[i] = true;
            col[j] = true;
            diag1[j - i + n - 1] = true;
            diag2[j + i] = true;
        }
    }
}

int main() {
    in >> n;
    place_dama(0, -1);
    out << sol << '\n';
    return 0;
}