#include <bits/stdc++.h>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int n, x[15], sol[15], nrsol, k;
bool first, ok;

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

void copyy()
{
    for(int i = 1; i <= n; i ++)
        sol[i] = x[i];
}

int Back()
{
    k = 1;
    x[k] = 0;
    nrsol = 0;
    first = 1;
    while(k > 0)
    {
        ok = 0;
        while(x[k] < n && !ok)
        {
            x[k]++;
            ok = valid(k);
        }
        if(ok == 0)
            k--;
        else
        {
            if(k == n) ///daca am pus toate damele pe tabla
            {
                if(first)
                {
                    copyy();
                    first = 0;
                }
                nrsol++;
            }
            else
            {
                k++;
                x[k] = 0;
            }
        }
    }
    return nrsol;
}

int main()
{
    fin >> n;
    nrsol = Back();
    for(int i = 1; i <= n; i ++)
        fout << sol[i] << " ";
    fout << '\n';
    fout << nrsol;
    return 0;
}