#include <fstream>
#include <cmath>

using namespace std;

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

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

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

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

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

            if (solutie (k))
            {
                ++ nrsol;

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

                    g << '\n';
                }
            }
            else
                back (k + 1);

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

int main()
{
    f >> n;

    back (1);

    g << nrsol;

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