Write a program to compute the number of ways to place n queens on an n × 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:

largeboard,
showmover=false,
label=false,
maxfield=d4,
setpieces=qa2,qb4,qc1,qd3
largeboard,
showmover=false,
label=false,
maxfield=d4,
setpieces=qa3,qb1,qc4,qd2

Input

Input consists of a natural number n > 0.

Output

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

Public test cases

**Input**

8

**Output**

92

**Input**

11

**Output**

2680

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C C++