#include<cstdio>
using namespace std;
int nr=0,sol[40],col[40],dp[40],ds[40],n;
void backtracking(int k){
    if(k==n+1){
        int i;
        nr++;
        if(nr==1)
            for(i=1;i<=n;i++){
                printf("%d",sol[i]);
                if(i==n)
                    printf("\n");
                else
                    printf(" ");
            }
        return;
    }
    int c;
    for(c=1;c<=n;c++)
        if(col[c]==0&&dp[c-k+n-2]==0&&ds[k+c-1]==0){
            sol[k]=c;
            col[c]=dp[c-k+n-2]=ds[k+c-1]=1;
            backtracking(k+1);
            col[c]=dp[c-k+n-2]=ds[k+c-1]=0;
        }
}
int main (){
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    backtracking(1);
    printf("%d",nr);
    return 0;
}