#include<cstdio>
int n,i,j,fr[25],x[25],nr;
FILE *f,*g;
int modul(int a){
    if(a<0)
        return -a;
    return a;
}
void back(int k){
    int i,j,ok;
    if(k==n+1){
        if(nr==0){
            for(i=1;i<=n;i++){
                fprintf(g,"%d ",x[i]);
            }
            fprintf(g,"\n");
        }
        nr++;
        return;
    }
    for(i=1;i<=n;i++){
        if(fr[i]==0){
            ok=1;
            for(j=1;j<k;j++){
                if(modul(k-j)==modul(x[j]-i)){
                    ok=0;
                    break;
                }
            }
            if(ok==1){
                x[k]=i;
                fr[i]=1;
                back(k+1);
                fr[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;
}