A fortress wall is an n-by-n grid of squares. Some squares are blocked by rubble and cannot hold a turret. A valid defense places n turrets, each attacking like a chess queen (along rows, columns, and both diagonals), so that no two turrets attack each other and no turret sits on a blocked square.
Count the number of valid defenses.
Input format
Line 1: two integers n and b, the board size and the number of blocked squares.
Next b lines: each two integers r and c (0-indexed row and column) of a blocked square. All blocked squares are distinct and lie on the board.
Output format
A single integer: the number of valid defenses.
Constraints
- 0 <= n <= 8
- 0 <= b <= n*n
- 0 <= r, c < n