#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>

using namespace std;

int N,Cnt;
int Sol[14],St[14],A[30],B[30];
bool V[14];

void Back(int K)
{
    if (K == N + 1)
    {
        if (!Cnt)
           for (int i = 1;i <= N;i++)
               Sol[i] = St[i];

        Cnt++;
    }

    for (int i = 1;i <= N;i++)
        if (!V[i] && !A[N - K + i] && !B[K + i - 1])
        {
            St[K] = i;
            V[i] = A[N - K + i] = B[K + i - 1] = 1;
            Back(K + 1);
            V[i] = A[N - K + i] = B[K + i - 1] = 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",Cnt);

  return 0;
}