#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], diagonala[15];

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

    for (int i = line, j = column; i > 0 && j > 0; i--, j--)
        if (tabla[i][j])
        return false;

    for (int i = line, j = column; i <= n && j > 0; i++, j--)
        if (tabla[i][j])
        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;

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

            tabla[i][col] = 0;
            linia[i] = 0;
        }
    }

    return res;
}


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