#include <cstdio>

using namespace std;

#define NMAX 100

int N,ans;
int Linie[NMAX],mainDiag[NMAX],secondDiag[NMAX],sol[NMAX];

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

void back(int k)
{
    if (k>N)
    {
        ++ans ;
        if (ans==1) 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);

    return 0;
}