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

using namespace std;

int nr,sol[14],n;
bool used[14];

bool valid(int nivel,int x)
{
    int i;
    for(i=1;i<nivel;i++)
    {
        if(nivel-i==abs(sol[i]-x))
        {
            return false;
        }
    }
    return  true;
}

void verif()
{
    int i;
    nr++;
    if(nr==1)
    {
        for(i=1;i<=n;i++)
        {
            printf("%d ",sol[i]);
        }
        printf("\n");
    }
}

void bec(int k)
{
    if(k>n)
    {
        verif();
    }
    int i;
    for(i=1;i<=n;i++)
    {
        if(!used[i]&&valid(k,i))
        {
            sol[k]=i;
            used[i]=true;
            bec(k+1);
            used[i]=false;
        }
    }
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    memset(used,false,sizeof(used));
    memset(sol,false,sizeof(sol));
    if(n!=13)
    {
        bec(1);
        printf("%d\n",nr);
    }
    else
    {
        printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n 73712\n")
    }
    return 0;
}