#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(V[i] == x) return 0;
        if(i+V[i] == top+x) return 0;
        if(i-V[i] == top-x) return 0;
    }
    return 1;
}

void Back(int top)
{
    int i;
    for(i=1; i<=N; i++)
    {
        if(!Check(top,i)) continue;
        V[top]=i;
        if(top==N)
        {
            NrSol++;
            if(Sol[1]) return;
            memcpy(Sol,V,sizeof(V));
        }
        else Back(top+1);
    }
}

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

    scanf("%d",&N);

    Back(1);

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