#include <cstdio>

#define NMAX 17

using namespace std;
int n, sol, poz[NMAX];
bool found, col[NMAX], diag1[2*NMAX], diag2[2*NMAX];
void back(int x)
{
    //printf("enter %d\n", x);
    if(x == n+1)
    {
        if(!found)
        {
            for(int i = 1; i<= n; ++i)
            {
                printf("%d ", poz[i]);
            }
            printf("\n");
            found = 1;
        }
        ++sol;
        return ;
    }
    for(int i = 1; i<= n; ++i)
    {
        //printf("poz = %d candidat %d\n", x, i);
        if(!col[i] && !diag1[n-x+i] && !diag2[x+i-1])
        {
            //printf("check candidat\n");
            poz[x] = i;
            col[i] = 1;
            diag1[n-x+i] = 1;
            diag2[x+i-1] = 1;
            back(x+1);
            col[i] = 0;
            diag1[n-x+i] = 0;
            diag2[x+i-1] = 0;
        }
    }
}

int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d", &n);
    back(1);
    printf("%d\n", sol);
    return 0;
}