#include <cmath>
#include <cstdio>

using namespace std;

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

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

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