#include<cstdio>
#include<cstring>

using namespace std;

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

bool 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 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)
        {
            ++NrSol;
            if(NrSol==1)
                for(i=1;i<=N;i++)
                    printf("%d ",V[i]);
            return;
        }
        else Back(top+1,mask | 1<<(i-1));
    }
}

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

    scanf("%d",&N);

    Back(1,0);

    printf("\n%d\n",NrSol);
    return 0;
}