Peaceful Queens

On a standard 8×8 chessboard, it is possible to arrange 8 queens such that none can attack another. Your task is to extend this concept to a chessboard of size n×n and determine how many ways you can place n queens so that no two queens threaten each other.

Input

The input consists of a single natural number n, where n does not exceed 10.

Output

The output should be a single integer representing the number of distinct arrangements of n queens on an n×n chessboard where no two queens can attack each other.

Examples