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

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

int x[14], sol[14];

bool posibil(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;
}

int calcul(int n)
{
    bool primul = true, valid = false;
    int k = 1, nrs = 1;
    while (k > 0)
    {
        valid = false;
        while ((x[k] < n) && !valid)
        {
            x[k]++;
            valid = posibil(k);
        }

        if (!valid)
            k--;
        else
        {
            if (k == n)
            {
                if (primul)
                {
                    memcpy(sol, x, sizeof(x));
                    primul = false;
                }
                nrs++;
            }
            else
            {
                k++;
                x[k] = 0;
            }
        }
    }
    return nrs;
}

int main()
{
    int n, nrsol, i;
    f >> n;
    nrsol = calcul(n);
    for (i = 1; i <= n; i++)
        g << sol[i] << " ";
    g << "\n" << nrsol;
    return 0;
}