#include <stdio.h>
#include <stdlib.h>
#define MAXN 13
#define DIR 4
FILE*fi,*fout;
int n,v[MAXN],con=0,flag=1,vf[MAXN+1],mat[MAXN][MAXN],dl[]={-1,-1,1,1},dc[]={-1,1,1,-1};
void bkt(int k){
    int i;
    if(k==n){
        if(flag==1){
            for(i=0;i<n;i++)
                fprintf(fout,"%d " ,v[i]);
            fprintf(fout,"\n");
            flag=0;
        }
        con++;
    }
    else
        for(i=0;i<n;i++)
             if(vf[i]==0&&gol(k,i)==0){
                  vf[i]=1;
                  mat[k][i]=1;
                  v[k]=i+1;
                  bkt(k+1);
                  mat[k][i]=0;
                  vf[i]=0;
             }
}
inline int gol(int l,int c){
    int i=0,l1,c1;
    while(i<DIR){
        l1=l+dl[i];
        c1=c+dc[i];
        while(l1>=0&&l1<n&&c1>=0&&c1<n&&mat[l1][c1]==0){
            l1=l1+dl[i];
            c1=c1+dc[i];
        }
        if(l1>=0&&l1<n&&c1>=0&&c1<n)
            i=DIR;
        i++;
    }
    if(mat[l1][c1]==1)
        return 1;
    else
        return 0;
}
int main(){
    fi=fopen("damesah.in" ,"r");
    fout=fopen("damesah.out" ,"w");
    fscanf(fi,"%d" ,&n);
    bkt(0);
    fprintf(fout,"%d" ,con);
    fclose(fi);
    fclose(fout);
    return 0;
}