# Appreciation

/*
 * Problem :: 9663 / N-Queen
 *
 * Kind :: Backtracking
 *
 * Insight
 * - 대표적인 Backtracking 문제이다
 *   + Brute Force 로 풀기에는 (N*N) 의 칸중 N 개를 뽑는 경우의 수를 모두 검사해야하므로
 *     엄청난 시간이 걸리게 된다
 *   + Queen 이 놓여진 자리의 가로, 세로, 양대각선은 다른 Queen 을 놓지 못하므로
 *     한 Queen 이 놓여진 후 다음 Queen 을 놓을 때 위와같은 사실을 이용하면
 *     검사해야 되는 경우의 수를 획기적으로 줄일 수 있다
 *     # 가로, 세로, 대각선(diagonal), 반대각선(anti-diagonal) 에
 *       Queen 이 놓여져 있는지 없는지를 검사해줌으로써
 *       현재 자리에 Queen 을 놓을 수 있는지를 알아보자
 *       -> 총 N 개의 Queen 을 성공적으로 놓았다면
 *          1 을 return 해 주어서 전체 가능한 경우의 수를 알아내자
 *
 * Point
 * - 각 행과 열에는 하나의 Queen 만 존재할 수 있으므로
 *   현재 행 또는 열에 Queen 을 놓았다면
 *   다음 행 또는 열로 이동해주자
 *   + 좌표를 기준으로 탐색을 진행할까 싶었는데
 *     이 경우 다음 행 또는 열로 바로 넘어가지 못하고
 *     남은 행 또는 열을 모두 탐색해야 하기 때문에 비효율적이다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N;
bool C[14], D[14*2-1], AD[14*2-1];

// Set up : Functions Declaration
int f(int R);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;

    // Process
    int ans = f(0);

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int f(int R)
/* R = 현재 행의 번호
 * 첫번째 행 - 0, 두번째 행 - 1, ..., 마지막 행 - N-1 */
{
    if (R == N) return 1; /* N 개의 Queen 을 모두 놓을 수 있는 경우를 발견 */
    int ret = 0; /* 지금까지 놓인 Queen 을 가지고
                  * R번 행부터 N-1번 행까지 N-R 개의 Queen 을 놓을 수 있는 경우의 수 */
    for (int i=0; i<N; i++) {
        int y = R; /* 현재 좌표의 y 값 */
        int x = i; /* 현재 좌표의 x 값 */

        /* C[a]  - (a-1)번째 열에 Queen 이 있으면 true, 없으면 false
         * D[b]  - 왼쪽 위에서 오른쪽 아래로 내려오는 사선
         *         (N-1,0) 을 지나는 사선이 0 번
         *         (N-1,1), (N-2,0) 을 지나는 사선이 1 번
         *         ...
         *         (0,N-1) 을 지나는 사선이 2*N-2 번
         *         b 는 (N-1-x) + y 로 구할 수 있음
         *         b 번 사선 위에 Queen 이 있으면 true, 없으면 false
         * AD[c] - 왼쪽 아래에서 오른쪽 위로 올라가는 사선
         *         (0,0) 을 지나는 사선이 0 번
         *         (1,0), (0,1) 을 지나는 사선이 1 번
         *         ...
         *         (N-1,N-1) 을 지나는 사선이 2*N-2 번
         *         c 는 x + y 로 구할 수 있음
         *         c 번 사선 위에 Queen 이 있으면 true, 없으면 false
         *
         * 참고로 대각선과 반대각선은 체스판의 정가운데를 기준으로 y 축 대칭
         * 그래서 c 에서 x 가 b 에서 N-1-x 임 */
        /* 열, 대각선, 반대각선 모두 Queen 이 놓여있지 않다면 */
        if (!C[x] && !D[N-1-x+y] && !AD[x+y]) {
            /* 현재 좌표에 Queen 을 놓음 */
            C[x] = D[N-1-x+y] = AD[x+y] = true;
            /* 다음 Queen 을 놓기 위해 다음 행으로 넘어감 */
            ret += f(R+1);
            /* 현재 좌표에 놓인 Queen 을 제거 */
            C[x] = D[N-1-x+y] = AD[x+y] = false;
        }
    }
    return ret;
}