#include <iostream>
#include <fstream>

using namespace std;

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

bool col[14], d1[27], d2[27];
int sol[14];
int n, s = 0;

void afisare()
{
    for(int i = 1; i <= n; ++i)
        g << sol[i] << " ";
}

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

void btk(int k)
{
    for(int i = 1; i <= n; i++)
    {

        sol[k] = i;
        if(!col[i] && !d1[i + k - 1] && !d2[n - i + k])
        {
            if(solutie(k))
            {
                if(s == 0)
                    {
                        afisare();
                        s++;
                    }
                else
                    s++;
            }
            else
                {
                    col[i] = d1[i + k - 1] = d2[n - i + k] = true;
                    btk(k + 1);
                    col[i] = d1[i + k - 1] = d2[n - i + k] = false;
                }
        }
    }
}
int main()
{
    f >> n;

    btk(1);

    g << "\n" << s;

    f.close();
    g.close();

    return 0;
}