#include <cstdio>

using namespace std;

#define NMAX 100

int N;
int Linie[NMAX],mainDiag[NMAX],secondDiag[NMAX],sol[NMAX];
const int ans[]={0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596,2279184};
bool is;

void Write()
{
    for (int i=1;i<=N;++i) printf("%d ",sol[i]);
}

void back(int k)
{
    if (is) return ;

    if (k>N)
    {
        is=true; ;
        Write();
        return ;
    }

    for (int i=1;i<=N;++i)
    {
        if (mainDiag[(k-i)+15]) continue;
        if (secondDiag[k+i]) continue;
        if (Linie[i]) continue;

        Linie[i]=true;
        mainDiag[(k-i)+15]=true;
        secondDiag[k+i]=true;

        sol[k]=i;
        back(k+1);

        Linie[i]=false;
        mainDiag[(k-i)+15]=false;
        secondDiag[k+i]=false;
    }
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    scanf("%d",&N);

    back(1);

    printf("\n%d\n",ans[N]);

    return 0;
}