#include <fstream>

using namespace std;

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

int n, nr, v[15];
bool col[15], d1[30], d2[30];

inline void bkt(int linie, int n)
{
    if (linie > n)
    {
        if (!nr)
        {
            for (int i = 1; i <= n; ++i)
                out << v[i] << " ";
            out << '\n';
        }
        ++nr;
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            if (!col[i] && !d1[linie + i] && !d2[i - linie + n - 1])
            {
                v[linie] = i;
                col[i] = d1[linie + i] = d2[i - linie + n - 1] = 1;
                bkt(linie + 1, n);
                col[i] = d1[linie + i] = d2[i - linie + n - 1] = 0;
            }
        }
    }
}

int main()
{
    in >> n;
    bkt(1, n);
    out << nr;
    return 0;
}