#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

int n, st[17], f[17], d[34], d2[34], nr_solutions;
int vect_sol[17];
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

void Afisare()
{
    int j;
    if (nr_solutions == 0)
    {
        for (j = 1; j <= n; j++)
            vect_sol[j] = st[j];
    }
    nr_solutions++;
}

void Printare()
{
    int j;
    for (j = 1; j <= n; j++)
        fout << vect_sol[j] << " ";
    fout << endl;
    fout << nr_solutions << endl;
}

void Back(int top)
{
    int i, j;
    if (top == n+1) Afisare();
    else
        for (i = 1; i <= n; i++)
            if (f[i] == 0 && d2[i+top] == 0)
            {
                if ((top > i && d[n - (top-i)] == 0) || (top <= i && d[n + (i-top)] == 0))
                {
                    /*
                    for (j = 1; j < 2*n-1; j++)
                    {
                        cout << d[j] << " ";
                    }
                    cout << endl;
                    */

                    st[top] = i;
                    f[i] = 1;
                    d2[st[top]+top] = 1;

                    if (top > st[top])
                        d[n - (top-st[top])] = 1;
                    else
                        d[n + (st[top]-top)] = 1;

                    Back(top+1);

                    f[i] = 0;
                    d2[st[top]+top] = 0;
                    if (top > st[top])
                        d[n - (top-st[top])] = 0;
                    else
                        d[n + (st[top]-top)] = 0;
                }
            }
}

int main ()
{
    fin >> n;
    Back(1);
    Printare();
    return 0;
}