#include <cstdio>

#define nMax 14
using namespace std;
int Sol[nMax], n, nrSol;
bool main_diag[2*nMax], sec_diag[2*nMax], col[nMax];
void write(int k)
{
    if(nrSol==0)
    {
        for(int i=1;i<=k;i++)
            printf("%d ", Sol[i]);
        printf("\n");
    }
    nrSol++;
}
void back(int k)
{
    for(int i=1;i<=n;i++)
    {
        if(main_diag[i+n-k]==0 && sec_diag[i+k-1]==0 && col[i]==0)
        {
            Sol[k]=i;
            main_diag[i+n-k]=sec_diag[i+k-1]=col[i]=1;
            if(k==n)
                write(k);
            back(k+1);
            main_diag[i+n-k]=sec_diag[i+k-1]=col[i]=0;
        }
    }
}
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    back(1);
    printf("%d", nrSol);
    return 0;
}