34500번 - Median of Medians 서브태스크다국어

문제

Busy Beaver has just learned about the Median of Medians algorithm! To better understand the algorithm, he has chosen an odd positive integer $N$ and wants to experiment with permutations of $\{1,2,\dots,3N\}$.¹

For any odd number $k$ and a sequence of distinct numbers $A = (a_1,a_2,\dots,a_k),ドル let $B = (b_1,b_2,\dots,b_k)$ be $A$ sorted in increasing order. Then, $\text{median}(a_1,a_2,\dots,a_k)$ is $b_{\frac{k+1}{2}},ドル the $\left(\frac{k+1}{2}\right)$-th element of $B$.

Busy Beaver thinks that a permutation of $(p_1,p_2,\dots,p_{3N})$ of $\{1,2,\dots,3N\}$ is nice if and only if

$$ \text{median}\Big(\text{median}(p_1, p_2, \dots, p_N),\text{median}(p_{N+1}, p_{N+2},\dots,p_{2N}),\text{median}(p_{2N+1},\dots,p_{3N})\Big) = \frac{3N+1}{2}. $$

Busy Beaver is extra picky with his permutations; he likes having certain numbers in certain positions. He has $M$ pairs of numbers $(a_i,b_i)$. A nice permutation $(p_1,p_2,\dots,p_{3N})$ is fitting if $p_{a_i} = b_i$ for all 1ドル \leq i \leq M$.

Help Busy Beaver determine the number of fitting permutations! Since the number of such permutations may be very large, compute the number of such permutations modulo 10ドル^9 + 7$.

¹A permutation of length $N$ is an array consisting of $N$ distinct integers from 1ドル$ to $N$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (2ドル$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($N=3$ but there is 4ドル$ in the array).

입력

Each test contains multiple test cases. The first line of input contains a single positive integer $T,ドル the number of test cases $(1 \leq T \leq 10^5)$. The description of each test case follows.

The first line of each test case contains two spaced positive integers $N$ and $M$ (1ドル \leq N \leq 3 \cdot 10^5,ドル 0ドル \leq M \leq 3N,ドル and $N$ is odd) --- the size of the permutation, and the number of pairs $(a_i, b_i),ドル respectively.

The next $M$ lines contain two positive integers $a_i, b_i$ (1ドル \leq a_i, b_i \leq 3N$) --- specifying that $p_{a_i} = b_i$. It is guaranteed that for all 1ドル \leq i < j \leq M,ドル $a_i \neq a_j$ and $b_i \neq b_j$.

It is guaranteed that the sum of $M$ across all test cases is no more than 10ドル^6$.

Note that there is no additional guarantee on the sum of $N$ across all test cases.

출력

For each test case, output one line with a single integer, indicating the number of fitting permutations modulo 10ドル^9 + 7$.

제한

서브태스크

노트

In the first test case, $N=1,ドル so we are working with permutations of length 3ドルN = 3$. Since $M=0,ドル we have no additional constraints on the permutation. One can check that for all permutations of length 3ドル,ドル computing the median of the medians gives the correct median of 2ドル,ドル so there are 6ドル$ fitting permutations.

In the second test case, $N=3,ドル so we are working with permutations of length 3ドルN = 9$. Since $M=9,ドル we have 9ドル$ constraints on the permutation, which have fixed all 9ドル$ elements of the permutation to $(1,2,3,4,5,6,7,8,9)$.

• The median of the first 3ドル$ elements $(1,2,3)$ is 2ドル$.
• The median of the middle 3ドル$ elements $(4,5,6)$ is 5ドル$.
• The median of the last 3ドル$ elements $(7,8,9)$ is 8ドル$.

The median of $(2,5,8)$ is 5ドル,ドル which is the correct median. Thus, there is exactly 1ドル$ fitting permutation, which is $(1,2,3,4,5,6,7,8,9)$.

In the third test case, $N=3,ドル so we are working with permutations of length 3ドルN = 9$. Since $M=6,ドル we have 6ドル$ constraints on the permutation, which have fixed the last 6ドル$ elements of the permutation to $(4,5,6,7,8,9)$. We are free to permute $(1,2,3)$ among the first 3ドル$ elements. Using a similar analysis as the second test case, we see that the following 6ドル$ permutations

• $(1,2,3,4,5,6,7,8,9)$
• $(1,3,2,4,5,6,7,8,9)$
• $(2,1,3,4,5,6,7,8,9)$
• $(2,3,1,4,5,6,7,8,9)$
• $(3,1,2,4,5,6,7,8,9)$
• $(3,2,1,4,5,6,7,8,9)$

are all fitting permutations.

In the fourth test case, $N=3,ドル so we are working with permutations of length 3ドルN = 9$. Since $M=3,ドル we have 3ドル$ constraints on the permutation, which have fixed the first 3ドル$ elements of the permutation to $(1,2,5)$. It can be checked that there are no fitting permutations that satisfy these constraints.