#include <iostream>
#include <fstream>

using namespace std;

int n, vizitat_coloana[14], d_jos[14], d_sus[14], d[30], poz_coloana[14], dame[14];
long long nr_sol;

void Citire()
{
    ifstream f("damesah.in");

    f >> n;
}

/**
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
*/

bool EsteLiber(int linie, int coloana)
{
    if(vizitat_coloana[coloana])
        return false;
    if(d[2 * n - linie - coloana])
        return false;
    if(linie >= coloana)
    {
        if(d_jos[linie - coloana])
            return false;
    }
    else
    {
        if(d_sus[coloana - linie])
            return false;
    }
    return true;
}

void Modificare(int linie, int coloana, int val)
{
    poz_coloana[linie] = coloana;
    vizitat_coloana[coloana] = val;
    d[2 * n - linie - coloana] = val;
    if(linie >= coloana)
        d_jos[linie - coloana] = val;
    else
        d_sus[coloana - linie] = val;
}

void Copiere()
{
    for(int i = 1; i <= n; i++)
        dame[i] = poz_coloana[i];
}

void Back(int linie)
{
    if(linie == n + 1)
    {
        if(nr_sol == 0)
            Copiere();
        nr_sol++;
    }
    else
    {
        for(int coloana = 1; coloana <= n; coloana++)
            if(EsteLiber(linie, coloana))
            {
                Modificare(linie, coloana, 1);
                Back(linie + 1);
                Modificare(linie, coloana, 0);
            }
    }
}

void Afisare()
{
    ofstream g("damesah.out");
    for(int i = 1; i <= n; i++)
        g << dame[i] << ' ';
    g << '\n' << nr_sol;
}

int main()
{
    Citire();
    Back(1);
    Afisare();

    return 0;
}