The problem of Queens#2712

The problem of Queens

1 second
64 megabytes
Very easy

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.

Input

The input contains a single natural number (N \leq 12).

Output

Output the required number of peaceful arrangements of queens.

Examples

Example 1

Loading
Loading