#include <cstdio>
#include <iostream>

using namespace std;

int N,st[20],sol[20],ans;
bool fr[20],frdiag1[50],frdiag2[50];

inline int Modul(int x)
{
    if(x<0)
        x=-x;
    return x;
}

inline bool Valid(int top)
{
    int i;
    if(fr[st[top]] || frdiag1[top-st[top]+N] || frdiag2[top+st[top]])
        return false;
    return true;
}

inline int Cmp(int a[], int b[])
{
    int i;
    for(i=1;i<=N && a[i]==b[i];++i);
    if(i==N+1)
        return 0;
    if(a[i]>b[i])
        return 1;
    return 2;
}

inline void Solve()
{
    int i;
    ++ans;
    if(sol[0]==0 || Cmp(sol,st)==1)
    {
        sol[0]=N;
        for(i=1;i<=N;++i)
            sol[i]=st[i];
    }
}

int main()
{
    int top,i;
    bool cand;
    freopen ("damesah.in","r",stdin);
    freopen ("damesah.out","w",stdout);
    scanf("%d", &N);
    top=1; st[top]=0;
    while(top>0)
    {
        cand=false;
        if(st[top])
        {
            fr[st[top]]=false;
            frdiag1[top-st[top]+N]=false;
            frdiag2[top+st[top]]=false;
        }
        while(!cand && st[top]<N)
        {
            ++st[top];
            cand=Valid(top);
        }
        if(!cand)
            --top;
        else
        {
            fr[st[top]]=true;
            frdiag1[top-st[top]+N]=true;
            frdiag2[top+st[top]]=true;
            if(top==N)
                Solve();
            else
                st[++top]=0;
        }
    }
    for(i=1;i<=N;++i)
        printf("%d ", sol[i]);
    printf("\n%d\n", ans);
    return 0;
}