#include<cstdio>
#include<cstring>

using namespace std;

int N,NrSol;
int V[15];
int Sol[15];

int Check(int top,int x)
{
    int i;
    for(i=1;i<=top-1;i++)
    {
        if(i+V[i] == top+x) return 0;
        if(i-V[i] == top-x) return 0;
    }
    return 1;
}

void Ok(int top)
{
    NrSol++;
    if(Sol[1]) return;
    memcpy(Sol,V,sizeof(V));
}

void Back(int top,int mask)
{
    int i;
    for(i=1;i<=N;i++)
    {
        if(mask & 1<<(i-1)) continue;
        if(!Check(top,i)) continue;
        V[top]=i;
        if(top==N) Ok(top);
        else Back(top+1,mask | 1<<(i-1));
    }
}

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

    scanf("%d",&N);

    Back(1,0);

    for(i=1;i<=N;i++)
        printf("%d ",Sol[i]);
    printf("\n%d\n",NrSol);
    return 0;
}