Queens (1) P16415

Write a program to compute the number of ways to place $n$ queens on an $n \times n$ chessboard so that no queen threatens another queen. That is, no two queens can be located on the same row, column or diagonal.

For instance, there are exactly two ways for $n = 4$:

Input

Input consists of a natural number $n > 0$.

Output

Print the number of ways to put $n$ queens on an $n \times n$ chessboard so that no queen threatens another queen.