#include <cstdio>

using namespace std;

int N,sol=0,i,j;
int v[15];
int c[15],d1[30],d2[30];

void bkt (int p)
{
    if (p==N+1)
    {
        if (sol==0)
        {
            for (i=1; i<=N; i++)
            {
                printf ("%d ",v[i]);
            }
            printf ("\n");
        }
        sol++;
    }
    else
    {
        for (j=1; j<=N; j++)
        {
            if (c[j]==0&&d1[j+N-p]==0&&d2[j+p-1]==0)
            {
                v[p]=j;
                c[j]=d1[j+N-p]=d2[j+p-1]=1;
                bkt(p+1);
                c[j]=d1[j+N-p]=d2[j+p-1]=0;
            }
        }
    }
}

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

    scanf ("%d",&N);

    bkt(1);

    printf ("%d\n",sol);

    return 0;
}