#include <cstdio>

#define maxN 13

using namespace std;

int n, nrSol, st[maxN+1], col[2*maxN+1], rd[2*maxN+1], ld[2*maxN+1];

void backt(int k){
    int i;
    if (k==n+1){
        nrSol++;
        if (nrSol<=1){
            for (i=1; i<=n; i++)
                printf("%d ", st[i]);
            printf("\n");
        }
    }else{
        for (i=1; i<=n; i++)
            if (col[i]==0 && ld[k-i+n-1]==0 && rd[k+i]==0){
                st[k]=i;
                col[i]=ld[k-i+n-1]=rd[k+i]=1;
                backt(k+1);
                col[i]=ld[k-i+n-1]=rd[k+i]=0;
            }
    }
}

int main(){
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    backt(1);
    printf("%d\n", nrSol);
    return 0;
}