#include <fstream>
#include <cmath>

using namespace std;

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

int n, sol[15], nrsol = 0, coloana[15], diagonala1[35], diagonala2[35];

bool valid (int k, int i)
{
    return ((coloana[i] == 1) && (diagonala1[k + i] == 1) && (diagonala2[k + n - i + 1] == 1));
}

bool solutie (int k)
{
    return (k == n);
}

void update ()
{
    ++ nrsol;

    if (nrsol == 1)
    {
        for (int i = 1; i <= n; i ++)
                g << sol[i] <<" ";

        g << '\n';
    }

}

void back (int k)
{
    for (int i = 1; i <= n; i ++)
    {
        sol[k] = i;
        ++ coloana[i];
        ++ diagonala1[k + i];
        ++ diagonala2[k + n - i + 1];

        if (valid (k, i))
        {
            if (solutie (k))
                update ();
            else
                back (k + 1);
        }

        -- coloana[i];
        -- diagonala1[k + i];
        -- diagonala2[k + n - i + 1];
    }
}

int main()
{
    f >> n;

    back (1);

    g << nrsol;

    f.close ();
    g.close ();
    return 0;
}