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

using namespace std;

int N,Cnt;
int Sol[14],St[14];
bool B[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 (!B[i])
        {
            bool ok = 1;
            B[i] = 1;
            St[K] = i;

            for (int j = K - 1;j;j--)
                if (abs(j - K) == abs(St[K] - St[j]))
                {
                    ok = 0;
                    break;
                }

            if (ok)
               Back(K + 1);

            B[i] = 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;
}