#include <fstream>

int n, v[30], k;
bool f[30], d1[30], d2[30];

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

void solve(int curr) {
    if (curr > n) {
        if (!k) {
            for (int i = 1; i <= n; i++) fout << v[i] << " ";
            fout << "\n";
        }
        k++;
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!f[i] and !d2[n - curr + i] and !d1[curr + i - 1]) {
            v[curr] = i;
            f[i] = d2[n - curr + i] = d1[curr + i - 1] = 1;
            solve(curr + 1);
            f[i] = d2[n - curr + i] = d1[curr + i - 1] = 0;
        }
}

int main() {
    fin >> n;
    solve(1);
    fout << k;
    return 0;
}