#include <stdio.h>

int n;
int poz[14];
int col[14];
int dp[25];
int ds[25];
bool ok;//este initializat cu fals
int nrsol;//este initializat cu 0
FILE *f;

void bkt(int lgc)//1 la apel
{
    int i;

    if (lgc == n+1)
    {
        if (!ok)
        {
            for (i=1; i<=n; i++)
                fprintf(f,"%d ",poz[i]);
            fprintf(f,"\n");
            ok=true;
        }
        nrsol++;
    }
    else
    {
        for (i=1; i<=n; i++)
        {
            if (!col[i] && !dp[n+i-lgc] && !ds[lgc+i-1])
            {
                poz[lgc]=i;
                col[i]=dp[n+i-lgc]=ds[lgc+i-1]=1;
                bkt(lgc+1);
                col[i]=dp[n+i-lgc]=ds[lgc+i-1]=0;
            }
        }
    }
}


int main()
{
    f=fopen("damesah.in","r");
    fscanf(f,"%d",&n);
    fclose(f);
    f=fopen("damesah.out","w");
    bkt(1);
    fprintf(f,"%d",nrsol);
    fclose(f);
}