You are probably familiar with the classical -queens problem: on an N \times N chessboard, it is required to place queens so that no two queens attack each other. Such an arrangement of queens is called a peaceful arrangement.
In this problem, we are interested not in just one peaceful arrangement, but in all distinct peaceful arrangements. More precisely, we seek the total number of such arrangements. For example, for an 8 \times 8 board, there are different peaceful arrangements of queens.
The input contains a single natural number (N \leq 12).
Output the required number of peaceful arrangements of queens.
Example 1