#include <fstream>
using namespace std;

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

const int N = 15;

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

void check() {
    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] && !a[k][i]) {
            used[i] = 1;
            v[k] = i;
            for (int j = 1; k + j <= n && (i - j > 0 || i + j <= n); ++j) {
                if (i - j > 0)
                    a[k + j][i - j] = 1;
                if (i + j <= n)
                    a[k + j][i + j] = 1;
            }
            if (k == n)
                check();
            else
                back (k + 1);
            used[i] = 0;
            for (int j = 1; k + j <= n && (i - j > 0 || i + j <= n); ++j) {
                if (i - j > 0)
                    a[k + j][i - j] = 0;
                if (i + j <= n)
                    a[k + j][i + j] = 0;
            }

        }
}

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