#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 afis()
{
    for(int i=1;i<=n;i++) printf("%d ",sol[i]);
    printf("\n");
}
void backtrack(int pos)
{
        for(int i=solp[pos-1]+1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if((col[j]||d1[diag1[i][j]]||d2[diag2[i][j]])==0)
                {
                    col[j]++;d1[diag1[i][j]]++;d2[diag2[i][j]]++;
                    solp[pos]=i;
                    if(as==0) sol[pos]=j;
                    if(pos<n) backtrack(pos+1);
                    else
                    {
                        if(as==0)
                        {
                            for(int i=1;i<=n;i++) printf("%d ",sol[i]);
                            printf("\n");
                            as=1;
                        }
                        ++ct;
                    }
                    col[j]--;d1[diag1[i][j]]--;d2[diag2[i][j]]--;
                }
            }
        }
}
int main()
{
    freopen ("damesah.in","r",stdin);
    freopen ("damesah.out","w",stdout);
    scanf("%d",&n);
    create_diag();
    backtrack(1);
    printf("%d\n",ct);
}