#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> col(13, true), diag1(2 * 13 - 1, true), diag2(2 * 13 - 1, true);
vector <int> coords(13, 0);

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

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