#include <fstream>

using namespace std;

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

int st[100], sol, n, k;
bool ev, as, ok;

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

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

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

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

void tipar()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            if(j == st[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 = 1;
                    sol++;
                }
                else sol++;
            }
            else
            {
                k++;
                init();
            }
        else k--;
    }
}

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