Note: The time limit for this problem is 4s, twice the default.

Moo! You are given an integer $N$ ($2\le N\le 2000$). Consider all permutations $p=[p_0,p_1,\dots, p_{N-1}]$ of $[0,1,2\dots, N-1]$. Let $f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|$ denote the minimum absolute difference between any two consecutive elements of $p$. and let $S$ denote the set of all $p$ that achieve the maximum possible value of $f(p)$

You are additionally given $K$ ($0\le K\le N$) constraints of the form $p_i=j$ ($0\le i,j < N$). Count the number of permutations in $S$ satisfying all constraints, modulo $10^9+7$.

Input Format

The first line contains $T$ ($1\le TN\le 2\cdot 10^4$) and $N$, meaning that you will need to solve $T$ independent test cases, each specified by a different set of constraints.

Each test case starts with $K$, followed by $K$ lines each containing $i$ and $j$. It is guaranteed that

• The same $i$ does not appear more than once within the same test case.
• The same $j$ does not appear more than once within the same test case.

Output Format

For each test case, the answer modulo $10^9+7$ on a separate line.

Sample Data

Sample Input

3 4
0
1
1 1
2
0 2
2 3

Sample Output

2
0
1

Sample Explanation

The maximum possible value of $f(p)$ is $2$, and $S=\{[2,0,3,1], [1,3,0,2]\}$.

Sample Input 2

9 11
2
0 5
6 9
3
0 5
6 9
1 0
4
0 5
6 9
1 0
4 7
5
0 5
6 9
1 0
4 7
2 6
6
0 5
6 9
1 0
4 7
2 6
9 3
7
0 5
6 9
1 0
4 7
2 6
9 3
5 2
8
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
9
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
10
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
8 10

Sample Output 2

6
6
1
1
1
1
1
1
1

Sample Explanation

$p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ should be counted for all test cases.

Sample Input 3

10 11
0
1
3 8
2
3 8
5 7
3
3 8
5 7
4 2
4
3 8
5 7
4 2
10 6
5
3 8
5 7
4 2
10 6
8 10
6
3 8
5 7
4 2
10 6
8 10
1 9
7
3 8
5 7
4 2
10 6
8 10
1 9
7 5
8
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
9
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
6 0

Sample Output 3

160
20
8
7
2
1
1
1
1
1

Sample Explanation

$p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ should be counted for all test cases.

Sample Input 4

5 987
3
654 321
543 210
432 106
2
654 321
543 210
1
654 321
1
0 493
0

Sample Output 4

0
538184948
693625420
932738155
251798971

Sample Explanation

Make sure to output the answer modulo $10^9+7$.

Constraints

• Input 5: $N=15$
• Input 6: $N=2000$
• Inputs 7-9: For all test cases, the constraint $p_0=\lfloor N/2\rfloor$ appears.
• Inputs 10-13: For all test cases, there exists some constraint $p_i = j$ with $j$ equal to $\lfloor N/2\rfloor$.
• Inputs 14-20: No additional constraints.

Problem credits: Benjamin Qi