#include<stdio.h>
#include<math.h>

int n, sol, col[15];
bool uzcol[15], uzdiag[2][30];

inline void Back(int line)
{
    int i;
    if(line == n + 1)
    {
        sol++;
        if(sol == 1)
        {
            for(i = 1; i <= n; ++i)
                printf("%d ", col[i]);
            printf("\n");
        }
        return;
    }
    for(i = 1; i <= n; ++i)
    {
        if(!uzcol[i] && !uzdiag[0][line + i] && !uzdiag[1][n - i + line])
        {
            col[line] = i;
            uzcol[i] = uzdiag[0][line + i] = uzdiag[1][n - i + line] = true;
            Back(line + 1);
            uzcol[i] = uzdiag[0][line + i] = uzdiag[1][n - i + line] = false;
        }
    }
}
 
int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    Back(1);
    printf("%d\n", sol);
    return 0;
}