#include<cstdio>
int n,pp,x;
int st[20],col[20],diag[20],diag2[20];
void back(int k)
    {if(k==n+1)
        {int i;
        if(pp==0)
            {for(i=1;i<=n;i++)
                printf("%d ",st[i]);
            printf("\n");
            pp=1;
            }
        x++;
        }
    else
        {int i;
        for(i=1;i<=n;i++)
            if(col[i]==0&&diag[i+k-1]==0&&diag2[k+n-i]==0)
                {st[k]=i;
                col[i]=1;
                diag[i+k-1]=1;
                diag2[k+n-i]=1;
                back(k+1);
                col[i]=0;
                diag[i+k-1]=0;
                diag2[k+n-i]=0;
                }
        }
    }
int main ()
{freopen ("damesah.in","r",stdin);
freopen ("damesah.out","w",stdout);
scanf("%d",&n);
back(1);
printf("%d",x);
return 0;
}