#include <bits/stdc++.h>

using namespace std;

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

const int N = 20;
int perm[N];
bool col[N], d1[2*N], d2[2*N];

int n, s;

void back(int pos) {

    if (pos > n) {
        s++;
        if (s == 1) {
            for (int i = 1; i <= n; ++i)
                fout << perm[i] << ' ';
            fout << '\n';
        }
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!col[i] && !d1[pos - i + n] && !d2[pos + i]) {
            col[i] = true;
            d1[pos - i + n] = true;
            d2[pos + i] = true;
            perm[pos] = i;
            back(pos + 1);
            col[i] = false;
            d1[pos - i + n] = false;
            d2[pos + i] = false;
        }
    }
}

int main() {

    fin >> n;
    back(1);
    fout << s;
    return 0;
}