#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int N,v[14];

int se_ataca(int i,int j)
{
    if(fabs(i-j) == fabs(v[i]-v[j]) ) return 1;
    return 0;
}

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

    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        v[i] = i;
    int bun,cnt = 0;

    do{
        bun = 1;
        for(int i = 2; i <= N; ++i)
        {
            for(int j = 1; j < i; ++j)
                if(se_ataca(j,i))
                {
                    bun = 0;
                    break;
                }
            if(!bun) break;
        }
        if(cnt == 0 && bun)
            for(int i = 1; i <= N; ++i) printf("%d ",v[i]);
         if(bun)
            ++cnt;

    }while(next_permutation(v+1,v+N+1));
    printf("\n%d\n",cnt);

    return 0;
}