#include <bits/stdc++.h>
using namespace std;

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

constexpr int NMAX = 13;
int n;
bool first = true;
int a[NMAX + 1], main_diag[NMAX * 2 + 1], sec_diag[NMAX * 2 + 1], col[NMAX + 1];

int backtrack(int l) {
    if (l == n + 1) {
        if (first) {
            first = false;
            for (int i = 1; i <= n; i++) {
                fout << a[i] << ' ';
            }
            fout << '\n';
        }
        return 1;
    }

    int ans = 0;
    for (int j = 1; j <= n; j++) {
        if (!col[j] && !main_diag[j - l + n] && !sec_diag[l + j]) {
            col[j] = main_diag[j - l + n] = sec_diag[l + j] = 1;
            a[l] = j;
            ans += backtrack(l + 1);
            col[j] = main_diag[j - l + n] = sec_diag[l + j] = 0;
        }
    }

    return ans;
}

int main() {
    fin >> n;
    fout << backtrack(1);
}