#include<cstdio>
using namespace std;
int sol,i,n,v[15],ap[15],ap1[40],ap2[40];
int d1(int x,int y){return x+y;}
int d2(int x,int y){return x-y+n;}
void Set(int poz,int i,int val){ap[i]=val;ap1[d1(poz,i)]=val;ap2[d2(poz,i)]=val;}
void back(int poz)
{
    if(poz==n+1)
    {
        sol++;
        if(sol==1)
        {
            for(i=1;i<=n;i++)
                printf("%d ",v[i]);
            printf("\n");
        }
        return ;
    }
    for(int i=1;i<=n;i++)
        if(ap[i]==0&&ap1[d1(poz,i)]==0&&ap2[d2(poz,i)]==0)
        {
            Set(poz,i,1);
            v[poz]=i;
            back(poz+1);
            Set(poz,i,0);
        }
}
int main()
{
freopen("damesah.in","r",stdin);
freopen("damesah.out","w",stdout);
scanf("%d",&n);
back(1);
printf("%d\n",sol);
return 0;
}