#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, i, j, k, l, m, nr;
int v[15];
int d1[50], d2[50];
int col[30], lin[30];
inline bool check(const int k) {
    const int ln = k, cl = v[k];
    if (col[cl] == 1) {
        return 0;
    }
    if (lin[ln] == 1) {
        return 0;
    }
    if (d1[ln - cl - 1 + 20] == 1) {
        return 0;
    }
    if (d2[ln + cl + 1] == 1) {
        return 0;
    }
    return 1;
}
inline void mod(const int k) {
    const int ln = k, cl = v[k];
    col[cl] = 1;
    lin[ln] = 1;
    d1[ln - cl - 1 + 20] = 1;
    d2[ln + cl + 1] = 1;
}
inline void unmod(const int k) {
    const int ln = k, cl = v[k];
    col[cl] = 0;
    lin[ln] = 0;
    d1[ln - cl - 1 + 20] = 0;
    d2[ln + cl + 1] = 0;
}
void afisare() {
    nr++;
    if (nr == 1) {
        for (int i = 1; i <= n; ++i) {
            fout << v[i] << ' ';
        }
        fout << '\n';
    }
}
void back(int k) {
    for (int i = 1; i <= n; ++i) {
        v[k] = i;
        int z = check(k);
        if (z) {
            if (k == n) {
                afisare();
            }
            else if (k < n) {
                mod(k);
                back(k + 1);
                unmod(k);
            }
        }
        v[k] = 0;
    }
}
int main() {
    fin >> n;
    back(1);
    fout << nr;
    fout.close();
    return 0;
}