#include <cstdio>
int diag1[20][20],diag2[20][20],solp[20],sol[20];
int as,ct,n,row[20],col[20],d1[20],d2[20];
inline void create_diag()
{
    int nt1=0,nt2=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            diag1[i][j]=diag1[i-1][j+1];
            if(diag1[i][j]==0) diag1[i][j]=++nt1;
            diag2[i][j]=diag2[i-1][j-1];
            if(diag2[i][j]==0) diag2[i][j]=++nt2;
        }
    }
}
void fill_b(int p1,int p2,int v)
{
    row[p1]+=v;
    col[p2]+=v;
    d1[diag1[p1][p2]]+=v;
    d2[diag2[p1][p2]]+=v;
}
void afis()
{
    for(int i=1;i<=n;i++) printf("%d ",sol[i]);
    printf("\n");
}
void backtrack(int pos)
{
    if(pos==n+1)
    {
        if(as==0)
        {
            afis();
            as=1;
        }
        ++ct;
    }
    else
    {
        for(int i=solp[pos-1]+1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(0==row[i]&&0==col[j]&&d1[diag1[i][j]]==0&&d2[diag2[i][j]]==0)
                {
                    fill_b(i,j,1);
                    sol[pos]=j;
                    solp[pos]=i;
                    backtrack(pos+1);
                    fill_b(i,j,-1);
                }
            }
        }
    }
}
int main()
{
    freopen ("damesah.in","r",stdin);
    freopen ("damesah.out","w",stdout);
    scanf("%d",&n);
    create_diag();
    backtrack(1);
    printf("%d\n",ct);
}