#include <cstdio>

using namespace std;
int nr,n,x,i,a[17],ne[17],pr[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++)
                printf ("%d ", a[i]);
        }
    }
    else
    {
        i=pr[0];
        while (i<=n)
        {
            if (p1[n+i-x]==false && s1[i+x]==false && l[i]==false)
            {
                p1[n+i-x]=s1[i+x]=l[i]=true;
                a[x]=i;
                ne[pr[i]]=ne[i];
                pr[ne[i]]=pr[i];
                back(x+1);
                ne[pr[i]]=i;
                pr[ne[i]]=i;
                p1[n+i-x]=s1[i+x]=l[i]=false;
            }
            i=ne[i];
        }
    }
}
int main()
{
    freopen ("damesah.in","r",stdin);
    freopen ("damesah.out","w",stdout);
    scanf ("%d", &n);
    pr[0]=1;
    for (i=1;i<=n;i++)
    {
        ne[i]=i+1;
        pr[i]=i-1;
    }
    back(1);
    printf ("\n%d", nr);
    return 0;
}