A royal court places n guards, each moving like a chess queen (any number of squares along a row, column, or diagonal), on an n-by-n board. A placement is safe if no two guards can attack each other: no two share a row, a column, or a diagonal.
Count how many distinct safe placements of exactly n guards exist on the board.
Input format
A single line: the integer n.
Output format
A single integer: the number of safe placements.
Constraints
- 0 <= n <= 12