#include <fstream>
#include <bitset>
#include <cmath>

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

const int nMax = 15;

int n, sol;
int dame[nMax];

bool notAfisat = true;

std::bitset<nMax> vis;

void Backtracking (int pos) {
//    for (int i = 1; i < pos; i += 1)
//        fout << dame[i] << ' ';
//    fout << '\n';

    if (pos <= n) {
        for (int i = 1; i <= n; i += 1) {
            if (vis[i] == 0) {
                bool good = true;
                for (int j = 1; j < pos && good; j += 1)
                    if (std::abs (j - pos) == std::abs (dame[j] - i))
                        good = false;
                if (good == true) {
                    dame[pos] = i, vis[i] = 1;
                    Backtracking (pos + 1), vis[i] = 0;
                }
            }
        }
    } else {
        if (notAfisat == true) {
            for (int i = 1; i <= n; i += 1)
                fout << dame[i] << ' ';
            fout << '\n';
            notAfisat = false;
        }
        sol += 1;
    }
}

int main () {
    fin >> n; Backtracking (1); fout << sol;
    return 0;
}