#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 col, lin, i, j;
    if(pas > n)
    {

        if(nrSol == 0)
        {
            for(i=1; i<=n; i++)
                printf("%d ", v[i]);
            printf("\n");
        }
        nrSol++;
        return;
    }
    for(col=1; col<=n; col++)
    {
        if(!mat[pas][col]) {
            v[pas] = col;
            for(lin=pas; lin<=n; lin++) {
                mat[lin][col]++;
                mat[lin][col+lin-pas]++;
                mat[lin][col-lin+pas]++;
            }
            bk(pas+1, n);
            for(lin=pas; lin<=n; lin++) {
                mat[lin][col]--;
                mat[lin][col+lin-pas]--;
                mat[lin][col-lin+pas]--;
            }
        }
    }
}