#include <cstdio>
#include <cstring>

using namespace std;
int N;
int v[20];
int used[20],used1[40],used2[40];
int sol[20],nrsol;

int abso(int k){
    if(k > 0) return k;
    return -k;
}

void Back(int k)
{
    if(k == N + 1){
        ++nrsol;
        if(nrsol == 1)
            memcpy(sol,v,sizeof(v));
        return;
    }

    for(v[k] = 1; v[k] <= N; ++v[k])
        if(!used[v[k]] && !used1[k - v[k] + 15] && !used2[k+v[k]])
        {
            used[v[k]] = 1;
            used1[k-v[k] + 15] = 1;
            used2[k+v[k]] = 1;

            Back(k+1);

            used[v[k]] = 0;
            used1[k-v[k] + 15] = 0;
            used2[k + v[k]] = 0;
        }
}

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

    scanf("%d",&N);
    Back(1);
    for(int i = 1; i <= N; ++i)
        printf("%d ",sol[i]);
    printf("\n%d\n",nrsol);

    return 0;
}