#include<fstream>
#define NMAX 30

using namespace std;

int n, solutie=0, sol[NMAX], a[NMAX], vz[NMAX], vzds[NMAX], vzdp[NMAX];

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

void Vizitare_ds(int k, int stare)
{
    int di, dj, x;
    di=k-1;
    dj=n-a[k];
    x=min(di, dj);
    di=k-x; dj=a[k]+x;
    if (di==1) vzds[dj]=stare;
    else vzds[di+n-1]=stare;
}

void Vizitare_dp(int k, int stare)
{
    int di, dj, x;
    di=k-1;
    dj=a[k]-1;
    x=min(di, dj);
    di=k-x; dj=a[k]-x;
    if (di==1) vzdp[dj]=stare;
    else vzdp[di+n-1]=stare;
}

bool vz_ds(int k)
{
    int di, dj, x;
    di=k-1;
    dj=n-a[k];
    x=min(di, dj);
    di=k-x; dj=a[k]+x;
    if (di==1) return vzds[dj];
    return vzds[di+n-1];
}

bool vz_dp(int k)
{
    int di, dj, x;
    di=k-1;
    dj=a[k]-1;
    x=min(di, dj);
    di=k-x; dj=a[k]-x;
    if (di==1) return vzdp[dj];
    return vzdp[di+n-1];
}

void Back(int k)
{
    int i;

    if (k==n+1)
    {
        if (!solutie)
        {
            solutie=1;
            for (i=1; i<=n; ++i) sol[i]=a[i];
        }
        else ++solutie;
    }
    else
        for (i=1; i<=n; ++i)
        {
            a[k]=i;
            if (!vz[i] && !vz_dp(k) &&!vz_ds(k))
            {
                vz[i]=1;
                Vizitare_ds(k, 1);
                Vizitare_dp(k, 1);
                Back(k+1);
                Vizitare_ds(k, 0);
                Vizitare_dp(k, 0);
                vz[i]=0;
            }
            a[k]=0;
        }
}

int main()
{
    f>>n;
    Back(1);
    int i;
    for (i=1; i<=n; ++i) g<<sol[i]<<" ";
    g<<"\n"<<solutie<<"\n";
    f.close();
    g.close();
    return 0;
}