#include <cstdio>

using namespace std;
int nr,n,x,i,a[17],b[17],p,s;
bool p1[30],s1[30],l[17];
void back (int x)
{
    int i;
    if (x==(n+1))
    {
        nr++;
        if (nr==1)
        {
            for (i=1;i<=n;i++)
                b[i]=a[i];
        }
    }
    for (i=1;i<=n;i++)
    {
        p=n+i-x;
        s=i+x;
        if (p1[p]==false && s1[s]==false && l[i]==false)
        {
            p1[p]=true;
            s1[s]=true;
            l[i]=true;
            a[x]=i;
            back(x+1);
            p=n+i-x;
            s=i+x;
            p1[p]=false;
            s1[s]=false;
            l[i]=false;
        }
    }
}
int main()
{
    freopen ("damesah.in","r",stdin);
    freopen ("damesah.out","w",stdout);
    scanf ("%d", &n);
    back(1);
    for (i=1;i<=n;i++)
        printf ("%d ", b[i]);
    printf ("\n%d", nr);
    return 0;
}