#include <cstdio>

using namespace std;
int nr,n,x,i,a[17],b[17];
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];
        }
    }
    else
    {
    for (i=1;i<=n;i++)
    {
        if (p1[n+i-x]==false && s1[i+x]==false && l[i]==false)
        {
            p1[n+i-x]=true;
            s1[i+x]=true;
            l[i]=true;
            a[x]=i;
            back(x+1);
            p1[n+i-x]=false;
            s1[i+x]=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;
}