#include <stdio.h>
#define MAXN 13
FILE *fout;
int v[MAXN],N,x,s,l;
char col[MAXN],diagpr[2*MAXN-1],diagsc[2*MAXN-1];
void finir(){
    int i,c;
    if((l==N)&&(x==0)){
        for(i=0;i<N;i++){
            fprintf(fout,"%d ",v[i]+1);
        }
        fprintf(fout,"\n");
        x++;
    }
    if(l==N){
        s++;
    }else{
        for(c=0;c<N;c++){
            if((col[c]==0)&&(diagpr[N+c-l-1]==0)&&(diagsc[N+N-l-c-2]==0)){
                col[c]=1;
                diagpr[N+c-l-1]=1;
                diagsc[N+N-l-c-2]=1;
                v[l]=c;
                l++;
                finir();
                l--;
                col[c]=0;
                diagpr[N+c-l-1]=0;
                diagsc[N+N-l-c-2]=0;
            }
        }
    }
    return ;
}
int main(){
    FILE *fin;
    fin=fopen("damesah.in","r");
    fout=fopen("damesah.out","w");
    fscanf(fin,"%d",&N);
    x=0;
    l=0;
    finir(N,fout);
    fprintf(fout,"%d\n",s);
    fclose(fin);
    fclose(fout);
    return 0;
}