#include <bits/stdc++.h>

using namespace std;

ifstream f ("damesah.in");
ofstream g ("damesah.out");

const int NMAX = 30;
const int aux = 15;
int n, ans;
int sol[NMAX];
bool col[NMAX], diag1[2 * NMAX], diag2[2 * NMAX];
bool first;

void write() {
    for (int i = 1; i <= n; ++i) {
            g << sol[i] << ' ';
    }
    g << '\n';
}

void backtr (int k) {
    if (k == n + 1) {
        if (first) {
            write();
            first = false;
        }
        ++ans;
    }
    for (int i = 1; i <= n; ++i) {
        if (!col[i] && !diag1[i + k - 1] && !diag2[k - i + aux]) {
            col[i] = 1;
            diag1[i + k - 1] = 1;
            diag2[k - i + aux] = 1;
            sol[k] = i;

            backtr(k + 1);

            col[i] = 0;
            diag1[i + k - 1] = 0;
            diag2[k - i + aux] = 0;
        }
    }
}

int main() {
    f >> n;
    first = true;
    backtr(1);
    g << ans << '\n';
    f.close();
    g.close();
    return 0;
}