#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

vector <int> Sol;

int N,Nr;
int S[20];
bool ok;
int UC[20],UDP[20],UDS[20];

void Back(int k)
{
    if(k==N+1)
    {
        Nr++;
        if(!ok)
        {
            ok=true;
            for(int i=1;i<=N;++i)
                    Sol.push_back(S[i]);
        }
        return;
    }
    for(int i=1;i<=N;++i)
    {
        if(!UC[i] && !UDP[N+k-i] && !UDS[k+i])
        {
            UC[i]=UDP[N+k-i]=UDS[k+i]=1;
            S[k]=i;
            Back(k+1);
            UC[i]=UDP[N+k-i]=UDS[k+i]=0;
        }
    }
}


int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&N);
    ok=false;
    Back(1);
    for(int i=0;i<Sol.size();++i)
        printf("%d ",Sol[i]);
    printf("\n%d",Nr);
    return 0;
}