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++