Page not loading? Try clicking here.
Placeholder

#1889

N Queen 1s 64MB

Problems

In chess, a queen can move any distance horizontally, vertically, or diagonally in a single move.

That is, when a queen is at the position marked X on the following chessboard, 

the next positions the queen can move to are one of the shaded areas.

An N \times N square chessboard is given. 

We want to place N queens on it such that no two queens can attack each other. 

How should the queens be placed? 

 

Output the total number of possible cases.


Input

Input the number of queens N (1≤N≤13).


Output

Output the number of ways to place N queens on an N \times N chessboard such that no two queens attack each other.


Example 

4
2


You must sign in to write code.