#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], diag_p[N * 2], diag_s[N * 2], ok = 1;

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

void check() {
    if (!sol)
        for (int i = 1; i <= n; ++i)
            fout << v[i] << " ";
    sol++;
}

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

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