#include <fstream>

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

int n, v[15], nr_sol, tabla[15][15];
bool linia[15], diagonala1[30], diagonala2[30];

bool is_safe (int line, int column) {
    if (linia[line])
    return false;

    if (diagonala1[line+column-1])
        return false;

    if (diagonala2[n-column+line])
        return false;

    return true;
}
bool rezolvare (int col) {
    if (col > n) {
        if (nr_sol == 0)
            for (int i = 1; i <= n; i++)
            fout << v[i] << " ";
        nr_sol++;
    }

    bool res = false;
    for (int i = 1; i <= n; i++) {
        if (is_safe(i, col)) {
            linia[i] = 1;
            tabla[i][col] = 1;
            v[col] = i;
            diagonala1[i+col-1] = 1;
            diagonala2[n-col+i] = 1;

            res = rezolvare(col+1) || res;

            tabla[i][col] = 0;
            linia[i] = 0;
            diagonala1[i+col-1] = 0;
            diagonala2[n-col+i] = 0;
        }
    }

    return res;
}


int main()
{
    fin >> n;
    rezolvare(1);
    fout << "\n" << nr_sol;
    return 0;
}