#include <bits/stdC++.h>

using namespace std;
int n,howmany;
vector<int>aux,rez;
bitset<20>col,dreapta,stanga;
int calc_dr(int x,int y)
{
    return x-y+1;
}
int calc_st(int x,int y)
{
    return y+x-1;
}
void bkk(int pos)
{
    if(pos>n)
    {
        howmany++;
        bool k=0;
        for(int i=0;i<n;i++)
        {
            if(rez[i]==aux[i])
                continue;
            if(rez[i]>aux[i])
                k=1;
            break;
        }
        if(k)
        {
            rez.clear();
            for(int i=0;i<n;i++)
                rez.push_back(aux[i]);
        }
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(col[i]==1)
                continue;
            int drept=calc_dr(i,pos);
            int stang=calc_st(i,pos);
            if(dreapta[drept]==1 || stanga[stang]==1)
                continue;
            dreapta[drept]=1;
            stanga[stang]=1;
            col[i]=1;
            aux.push_back(i);
            bkk(pos+1);
            aux.pop_back();
            col[i]=0;
            dreapta[drept]=0;
            stanga[stang]=0;
        }
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    rez.push_back(20);
    bkk(1);
    for(int i=0;i<n;i++)
        printf("%d ",rez[i]);
    printf("\n");
    printf("%d",howmany);
    return 0;
}