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





    fclose(f);
    fclose(g);
    return 0;
}