#include <cmath>
#include <iostream>
#include <cstdio>

using namespace std;

int n, sol[1000], lin, ok, nr;
int d2[60], d1[60], col[60];

void backt(int lin)
{
    int dd1, dd2;
    if(lin==n+1){
        if(ok==0){
            for(int i=1; i<=n;)
                printf("%d ", sol[i++]);
            printf("\n");
        }
        ok++;
        return;
    }
    for(int i=1; i<=n; i++)
    {
        dd1 = lin+i-1;
        dd2 = lin-i+n;
        if(!d1[dd1] && !d2[dd2] && !col[i])
        {
            sol[lin]=i;
            d1[dd1]=d2[dd2]=col[i]=1;
            backt(lin+1);
            d1[dd1]=d2[dd2]=col[i]=0;
        }
    }
}

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