Count Queen Placements

Given an integer n, return the number of ways to place n queens on an n x n board so that no two queens attack each other.

Two queens attack each other when they share a row, a column, or a diagonal, in either direction. Every valid placement therefore has exactly one queen in each row and each column, with no two queens on a common diagonal.

Two placements are different when any queen occupies a different square.

Examples

Example 1

Input: n = 4
Output: 2
Explanation: On a 4 x 4 board there are exactly two placements of 4 mutually non-attacking queens (each is the mirror image of the other).

Example 2

Input: n = 1
Output: 1
Explanation: A single queen on the single square attacks nothing.