You are certainly aware of the famous N-queens problem that consists on finding a safe placement for N queens on a N by N chessboard. We say that a configuration is safe when no queen can attack any other queen on the board.

In this problem your task has been simplified. We request that you determine the maximally safe configurations of queens on a N by N chessboard. A configuration is maximally safe if no queen can be added without the configuration becoming unsafe.

As an example, consider a 3x3 chessboard. In this case there are 9 different maximally safe configurations as illustrated in the following figure:

Input consists of an integer, N ≤ 10, corresponding to the size of the chessboard.

Output

Output consists of an integer corresponding to the number of different maximally safe configurations that exist.

Sample Input

3

9