#include <iostream>
#include <fstream>

using namespace std;

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

int n, x[20], prima[20];
long long nrsol = 0;
bool col[20], d1[40], d2[40];

void backt()
{
    int k = 1;
    x[1] = 0;
    while (k > 0)
    {
        if (x[k] < n)
        {
            x[k]++;
            int c = x[k];
            if (!col[c] && !d1[k - c + n] && !d2[k + c])
            {
                if (k == n)
                {
                    nrsol++;
                    if (nrsol == 1)
                        for (int i = 1; i <= n; i++)
                            prima[i] = x[i];
                }
                else
                {
                    col[c] = d1[k - c + n] = d2[k + c] = true;
                    x[++k] = 0;
                }
            }
        }
        else
        {
            k--;
            if (k > 0)
            {
                int c = x[k];
                col[c] = d1[k - c + n] = d2[k + c] = false;
            }
        }
    }
}

int main()
{
    f >> n;
    backt();
    for (int i = 1; i <= n; i++)
        g << prima[i] << ' ';
    g << '\n' << nrsol << '\n';
    return 0;
}