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