#include <cstdio>

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