#include<cstdio>
#include<cstring>

using namespace std;

int N,NrSol;
int V[15];
bool Distincte[15],DiagPr[30],DiagSec[30];

void Ok(int top)
{
    int i;
    NrSol++;
    if(NrSol==1)
        for(i=1; i<=N; i++)
            printf("%d ",V[i]);
}

void Back(int top)
{
    int i;
    if(top > N)
    {
        Ok(top);
        return;
    }
    for(i=1; i<=N; ++i)
    {
        if(Distincte[i]) continue;
        if(DiagPr[N+top-i]) continue;
        if(DiagSec[top+i]) continue;

        V[top]=i;
        Distincte[i]=1;
        DiagPr[N+top-i]=1;
        DiagSec[top+i]=1;

        Back(top+1);

        Distincte[i]=0;
        DiagPr[N+top-i]=0;
        DiagSec[top+i]=0;
    }
}

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

    scanf("%d",&N);

    Back(1);

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