#include <fstream>
#include <cmath>
using namespace std;

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

int st[15], sol = 0, n, k;
bool ev, as, ok;

void init()
{
    st[k] = 0;
}

bool succesor()
{
    if(st[k] < n)
    {
        st[k]++;
        as = true;
    }
    else
    {
        as = false;
    }
    return as;
}

bool valid()
{
    ev = true;
    for(int i = 1; i < k; i++)
    {
        if(st[k] == st[i] || abs(i - k) == abs(st[i] - st[k]))
        {
            ev = false;
            break;
        }
    }
    return ev;
}

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

void tipar()
{
    for(int i = 1; i <= n; i++)
    {
        g << st[i] << ' ';
    }
}

void bt()
{
    k = 1;
    init();
    while(k > 0)
    {
        do
        {
            as = succesor();
            if(as) ev = valid();
        }
        while(as && !ev);
        if(as)
        {
            if(solutie())
            {
                if(!ok)
                {
                    tipar();
                    ok = true;
                }
                sol++;
            }
            else
            {
                k++;
                init();
            }
        }
        else
        {
            k--;
        }
    }
}

int main()
{
    f >> n;
    bt();
    g << '\n' << sol;
    return 0;
}