#include<cstdio>
int n,li[100],co[100],d1[100],d2[100],nr,sl[100],m;
void bck(int x)
{
    int i,j;
    if(x<=n)
    {
        i=x;
        for(j=1;j<=n;j++)
        if(li[i]==0 && co[j]==0 && d1[i-j+n]==0 && d2[i-(n-j+1)+n]==0)
        {
            li[i]=1; co[j]=1; d1[i-j+n]=1; d2[i-(n-j+1)+n]=1;
            sl[x]=i*(n+1)+j;
            bck(x+1);
        li[i]=0; co[j]=0; d1[i-j+n]=0; d2[i-(n-j+1)+n]=0;
        }
    }
    else
    {
        nr++;
        if(nr==1)
        {
        for(i=1;i<=n;i++)
        printf("%d ",sl[i]%(n+1));
        }
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    nr=m=0;
    bck(1);
    printf("\n%d\n",nr);
    return 0;
}