#include <stdio.h>
#include <stdlib.h>
#define MAXN 13
int fc[MAXN+1];//frecventa pe coloane
int fmd[2*MAXN];//frecventa pe principale
int fsd[2*MAXN];//frecventa pe secundare
int sol[MAXN+1];//solutia generata
FILE *fin,*fout;
int n,nrsol;
void bkt(int l) {
    if(l==n) {
        if(nrsol==0) {
            for(int c=0; c<n; c++) {
                fprintf(fout,"%d ",sol[c]+1);
            }
            fputc('\n',fout);
        }
        nrsol++;
        return;
    }
    for(int c=0; c<n; c++) {
        if(fc[c]==0&&fmd[n-1+l-c]==0&&fsd[l+c]==0) {
            sol[l]=c;
            fc[c]=fmd[n-1+l-c]=fsd[l+c]=1;
            bkt(l+1);
            fc[c]=fmd[n-1+l-c]=fsd[l+c]=0;
        }
    }
}
int main() {
    fin=fopen("damesah.in","r");
    fscanf(fin,"%d",&n);
    fclose(fin);
    fout=fopen("damesah.out","w");
    bkt(0);
    fprintf(fout,"%d",nrsol);
    fclose(fout);
    return 0;
}