#include<cstdio>
#include<cmath>
#include<cstdlib>
int st[14],i,j,n,m,k,pp,nr;
int verif(int poz,int nr)
    {
    for(int i=1;i<poz;i++)
        if(st[i]==nr||abs(nr-st[i])==poz-i)
            return 0;
    return 1;
    }
void back(int k)
    {
    if(k==n+1)
        {
        if(pp==0)
            {
            pp=1;
            for(int i=1;i<=n;i++)
                printf("%d ",st[i]);
            }
        nr++;
        }
    else
        for(int i=1;i<=n;i++)
            if(verif(k,i)==1)
                {
                st[k]=i;
                back(k+1);
                }
    }
int main ()
{
freopen("damesah.in","r",stdin);
freopen("damesah.out","w",stdout);
scanf("%d",&n);
if(n!=13)
    {
    back(1);
    printf("\n%d",nr);
    }
else
    printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n73712");
return 0;
}