#include <cstdio>

using namespace std;

const int MAX = 20;

int v[MAX], mat[MAX][MAX], nrSol;

bool correctPos(int n);
void bk(int pas, int n);

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

    int n;
    scanf("%d", &n);
    bk(1, n);
    printf("%d", nrSol);
    return 0;
}
void bk(int pas, int n)
{
    int i, j;
    if(pas > n)
    {
        for(i=1; i<=n; i++)
            mat[i][v[i]] = 1;
        if(correctPos(n))
        {
            if(nrSol == 0)
            {
                for(i=1; i<=n; i++)
                    printf("%d ", v[i]);
                printf("\n");
            }
            nrSol++;
        }
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                mat[i][j] = 0;
        return;
    }
    for(i=1; i<=n; i++)
    {
        v[pas] = i;
        bk(pas+1, n);
    }
}
bool correctPos(int n)
{
    int i, k, lin, cola, colb;
    for(k=1; k<=n; k++)
    {
        cola = colb = v[k];
        lin = k;
        do
        {
            lin++;
            if(cola > 1)
            {
                cola--;
                if(mat[lin][cola])
                    return 0;
            }
            if(colb < n)
            {
                colb++;
                if(mat[lin][colb])
                    return 0;
            }


            if(mat[lin][v[k]])
                return 0;
        }while(lin < n);

    }
    return 1;
}