#include <fstream>
using namespace std;

int queen[15], coloana[15], diag_sec[30], diag_princ[30], sol, n;
ofstream out("damesah.out");

void back (int lin)
{
    if (lin - 1 == n)
    {
        if (!sol)
        {
            for (int i = 1; i < lin; ++i)
                out << queen[i] << " ";
            out << "\n";
        }
        ++sol;
    }
    for (int col = 1; col <= n; ++col)
    {
        queen[lin] = col;
        if (coloana[col] == 0 && diag_princ[col - lin + n] == 0 && diag_sec[col + lin - 1] == 0)
        {
            coloana[col] = 1;
            diag_princ[col - lin + n] = 1;
            diag_sec[col + lin - 1] = 1;

            back(lin + 1);

            coloana[col] = 0;
            diag_princ[col - lin + n] = 0;
            diag_sec[col + lin - 1] = 0;
        }
    }
}

int main()
{
    ifstream in("damesah.in");
    in >> n;
    in.close();
    back(1);
    out << sol;
    out.close();
    return 0;
}