311258: CF1957C. How Does the Rook Move?

C. How Does the Rook Move?time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

3
331
671968183

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.

题目大意：
在国际象棋中，白车和黑车交替放置在一个n×n的棋盘上，确保任何两个车都不会相互攻击。两个车会相互攻击如果它们在同一行或同一列（不论颜色）。有效的移动是将车放在(r, c)的位置，使其不攻击任何其他车。你先走，每次你走完后，电脑会镜像地放置黑车。如果r=c，则电脑无法镜像你的移动，并跳过其回合。你已经和电脑走了k步，必须继续玩游戏，直到没有有效的移动为止。在k步之后继续游戏时，有多少不同的最终配置是可能的？保证k步和隐含的电脑步都是有效的。由于答案可能很大，请以10^9+7为模输出。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含两个整数n和k（1≤n≤3×10^5，0≤k≤n）——棋盘的大小和你已经玩的步数。
- 接下来的k行，每行包含两个整数r_i和c_i，表示你的第i步移动。
- 保证k步和隐含的电脑步都是有效的。
- 保证所有测试用例的n之和不超过3×10^5。

输出：
- 对于每个测试用例，输出一个整数，即可能的最终配置的总数模10^9+7。题目大意： 在国际象棋中，白车和黑车交替放置在一个n×n的棋盘上，确保任何两个车都不会相互攻击。两个车会相互攻击如果它们在同一行或同一列（不论颜色）。有效的移动是将车放在(r, c)的位置，使其不攻击任何其他车。你先走，每次你走完后，电脑会镜像地放置黑车。如果r=c，则电脑无法镜像你的移动，并跳过其回合。你已经和电脑走了k步，必须继续玩游戏，直到没有有效的移动为止。在k步之后继续游戏时，有多少不同的最终配置是可能的？保证k步和隐含的电脑步都是有效的。由于答案可能很大，请以10^9+7为模输出。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含两个整数n和k（1≤n≤3×10^5，0≤k≤n）——棋盘的大小和你已经玩的步数。 - 接下来的k行，每行包含两个整数r_i和c_i，表示你的第i步移动。 - 保证k步和隐含的电脑步都是有效的。 - 保证所有测试用例的n之和不超过3×10^5。 输出： - 对于每个测试用例，输出一个整数，即可能的最终配置的总数模10^9+7。