#include <iostream>
#include <cstdio>
#define NR 100005
using namespace std;

int vizColoana[NR],vizDiagonalaP[NR],vizDiagonalaS[NR],prim,sol[NR],nrSol,n;

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


void backTR(int k)
{
    if(k==n+1)
    {
        nrSol++;
        if(prim==0)
        afisare();
        prim=1;
        return;
    }
    for(int i=1;i<=n;i++)
        if(!vizColoana[i]&&!vizDiagonalaP[n+k-i]&&!vizDiagonalaS[k+i])
    {
        sol[k]=i;
        vizColoana[i]=1;
        vizDiagonalaP[n+k-i]=1;
        vizDiagonalaS[k+i]=1;

        backTR(k+1);

        vizColoana[i]=0;
        vizDiagonalaP[n+k-i]=0;
        vizDiagonalaS[k+i]=0;
    }
}



int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    backTR(1);
    printf("\n%d",nrSol);

    return 0;
}