How Does the Rook Move?
Contest: Codeforces Round 940 (Div. 2) and CodeCraft-23
Difficulty rating: 1600
Tags: combinatorics, dp, math

You are given an $$$n \times n$$$ chessboard where you and the computer take turns alternatingly to place white rooks & black rooks on the board respectively. While placing rooks, you have to ensure that no two rooks attack each other. Two rooks attack each other if they share the same row or column regardless of color.

A valid move is placing a rook on a position ($$$r$$$, $$$c$$$) such that it doesn't attack any other rook.

You start first, and when you make a valid move in your turn, placing a white rook at position ($$$r$$$, $$$c$$$), the computer will mirror you and place a black rook at position ($$$c$$$, $$$r$$$) in its turn. If $$$r = c$$$, then the computer can't mirror your move, and skips its turn.

You have already played $$$k$$$ moves with the computer (the computer tries to mirror these moves too), and you must continue playing the game until there are no valid moves remaining. How many different final configurations are possible when you continue the game after the $$$k$$$ moves? It is guaranteed that the $$$k$$$ moves and the implied computer moves are valid. Since the answer may be large, print it modulo $$$10^9+7$$$.

Two configurations are considered different if there exists a coordinate ($$$r$$$, $$$c$$$) which has a rook in one configuration, but not in the other or the color of the rook on the coordinate is different.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$0 \leq k \leq n$$$) — the size of the chessboard and the number of moves you have already played respectively.

Each of the next $$$k$$$ lines of the test case contains two integers $$$r_i$$$ and $$$c_i$$$, denoting the $$$i$$$-th move you made.

It is guaranteed that the $$$k$$$ moves and the implied computer moves are valid.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output a single integer on a new line — the total number of possible final configurations modulo $$$10^9+7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we have a $$$4 \times 4$$$ grid and you've already played $$$1$$$ move. After you and the computer play a turn, we have a white rook at ($$$1$$$, $$$2$$$), and a black rook at ($$$2$$$, $$$1$$$). There are three possible configurations from this state —

1. You place a white rook at ($$$3$$$, $$$4$$$) and the computer places a black rook at ($$$4$$$, $$$3$$$) as a response.
2. You place a white rook at ($$$4$$$, $$$3$$$) and the computer places a black rook at ($$$3$$$, $$$4$$$) as a response.
3. You place a white rook at ($$$3$$$, $$$3$$$) and then at ($$$4$$$, $$$4$$$), or the other way around. They both result in the same configuration.

Example input:
3
4 1
1 2
8 1
7 6
1000 4
4 4
952 343
222 333
90 91

Example output:
3
331
671968183

Editorial:
There are essentially two types of moves:
1. Placing a rook at some $$$(i, i)$$$: This reduces the number of free rows and columns available by $$$1$$$.
2. Placing a rook at some $$$(i, j)$$$, where $$$i \neq j$$$: The computer now mirrors this by placing a rook at $$$(j, i)$$$, blocking rows $$$i$$$ and $$$j$$$ along with columns $$$i$$$ and $$$j$$$. So the number of free rows and columns is reduced by $$$2$$$.
First, we account for the $$$k$$$ moves played earlier and count the number of free columns/rows remaining to place rooks in, and call it $$$m$$$.
Notice that the order of removing rows/columns doesn't affect the final configuration of rooks, and hence only the count of rows matters, to determine the number of final configurations.
We can use a dynamic programming approach where $$$dp[i]$$$ represents the number of final configurations when $$$i$$$ rows and columns are left.
Since the order of removing rows/columns is unimportant, let's start by removing the last row or column.
When removing the last row or column in an $$$i \times i$$$ grid, we have two options:
• We place a rook $$$(i, i)$$$, resulting in the deletion of only the last row and column leaving an $$$(i-1) \times (i-1)$$$ grid. The number of final configurations in this case are given by $$$dp[i-1]$$$.
• Alternatively, we can place a rook at $$$(i, j)$$$ or $$$(j, i)$$$ for any $$$j \in \{1, 2, \ldots, i-1\}$$$. After this move, both the $$$j$$$-th and the $$$i$$$-th rows and columns are deleted, leaving an $$$(i-2) \times (i-2)$$$ grid. This contributes $$$2 (i-1) \cdot dp[i-2]$$$ to $$$dp[i]$$$.
Overall, we compute $$$dp[i] = dp[i-1] + 2 (i-1) \cdot dp[i-2]$$$ for all $$$i \in \{2, 3, \ldots, n\}$$$, with the base case of $$$dp[0] = dp[1] = 1$$$.
Our final answer is $$$dp[m]$$$.