#include<cstdio>
int n,i,j,nr,c[50],v[50],d1[50],d2[50];
FILE *f,*g;
void back(int k){
    if(k==n+1){
        nr++;
        if(nr==1){
            for(i=1;i<=n;i++){
                fprintf(g,"%d ",v[i]);
            }
            fprintf(g,"\n");
        }
        return;
    }
    for(int i=1;i<=n;i++){
        if( c[i] == 0 && d1[k+i] == 0 && d2[n+k-i] == 0 ){
            c[i]=d1[k+i]=d2[n+k-i]=1;
            v[k]=i;
            back(k+1);
            c[i]=d1[k+i]=d2[n+k-i]=0;
        }
    }
}
int main(){
    f=fopen("damesah.in","r");
    g=fopen("damesah.out","w");
    fscanf(f,"%d",&n);
    back(1);
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}