#include <stdio.h>
#include <stdlib.h>
int v[17],f[17],perm=0,diag1[400],diag2[400];
void bkt(int n,int p)
{
    int i,j,g1,g2,x;
    if(p==n+1){
        perm++;
        if(perm<=1){
            for(i=1; i<=n; i++)
                printf("%d ",v[i]);
            putchar('\n');
        }
    }
    else
    {
        for(x=1; x<=n; x++)
        {
            v[p]=x;
            if(p>x)
                g1=n-(p-x);
            else
                g1=n+(x-p);
            if(p>n-x)
                g2=n+(p-(n-x))-1;
            else
                g2=(n-x)-p+1;
            if(f[v[p]]==0 && diag2[g2]==0 && diag1[g1]==0){
                f[v[p]]=1;
                diag1[g1]=1;
                diag2[g2]=1;
                bkt(n,p+1);
                diag1[g1]=0;
                diag2[g2]=0;
                f[v[p]]=0;
            }
        }

    }

}
int main()
{
    int i,n;
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    bkt(n,1);
    printf("%d\n",perm);

    return 0;
}