#include <fstream>

using namespace std;
int n, ok = 1, sol;
int x[30], f[30];

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


int verif(int pas) {
    for (int i = 1; i < pas; i++)
        if (pas - i == abs(x[pas] - x[i]))
            return 0;
    return 1;
}

void backtrack(int pas) {
    if (pas == n + 1) {
        sol++;
        if (ok == 1) {
            for (int i = 1; i <= n; i++) {
                fout << x[i] << " ";
            }
            ok = 0;
        }
    } else
        for (int i = 1; i <= n; i++) {
            if (f[i] == 0) {
                x[pas] = i;
                f[i] = 1;
                if (verif(pas)) {
                    backtrack(pas + 1);
                }
                f[i] = 0;
            }
        }
}

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