#include <cstdio>
using namespace std;
int n, sol[20], lin, ok, nr, ii;
bool d2[40], d1[40], col[40];

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

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