A security team wants to place n motion sensors on an n-by-n grid of rooms, one per row and one per column, such that no two sensors share a row, a column, or a diagonal (sensors sweep entire rows, columns, and both diagonal directions). This is exactly the classic non-attacking-queens placement rule.
Count the number of distinct ways to place n sensors on the n-by-n grid so that no two attack each other.
Input format
Line 1: a single integer n.
Output format
A single integer: the number of valid placements.
Constraints
- 1 ≤ n ≤ 8