#include <cstdio>
int diag1[20][20],diag2[20][20],solp[20],sol[20];
int as,ct,n;
int col,d1,d2;
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&(1<<j))==0&&(d1&(1<<diag1[i][j]))==0&&(d2&(1<<diag2[i][j]))==0)
                {
                    col^=(1<<j);d1^=(1<<diag1[i][j]);d2^=(1<<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^=(1<<j);d1^=(1<<diag1[i][j]);d2^=(1<<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);
}