#include <fstream>
using namespace std;

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

const int N = 15;

int v[N], n, sol;
bool used[N], ok = 1;

int abs(int x) {
    return x > -x ? x : -x;
}

void check() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; i + j <= n; ++j)
            if (abs(v[i] - v[i+j]) == j)
                return;
    if (ok)
        for (int i = 1; i <= n; ++i)
            fout << v[i] << " ";
    ok = 0;
    sol++;
}

void back(int k) {
    for (int i = 1; i <= n; ++i)
        if (!used[i]) {
            used[i] = 1;
            v[k] = i;
            if (k == n)
                check();
            else
                back (k + 1);
            used[i] = 0;
        }
}

int main() {
    fin >> n;
    back (1);
    fout << "\n" << sol;
}