#include <bits/stdc++.h>
using namespace std;
void DAU(const string& task = "") {
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
        freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PLEC() {
    exit(0);
}
const int N(100);
int n, res, st[N];
bool afis, d1[N], d2[N], col[N];
inline void Back(const int& j) {
    if (j == n + 1) {
        if (!afis) {
            for (int i = 1; i <= n; ++i)
                cout << st[i] << ' ';
            cout << '\n';
            afis = true;
        }
        ++res;
        return;
    }
    for (int i = 1; i <= n; ++i)
        if (!col[i] && !d1[j - i + n] && !d2[j + i - 1]) {
            col[i] = d1[j - i + n] = d2[j + i - 1] = true;
            st[j] = i;
            Back(j + 1);
            col[i] = d1[j - i + n] = d2[j + i - 1] = false;
        }
}
signed main() {
    DAU("damesah");
    cin >> n;
    Back(1);
    cout << res;
    PLEC();
}