문제

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$.

입력

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.

출력

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

예제 입력 1

3 4
0
1
1 1
2
0 2
2 3

예제 출력 1

2
0
1

예제 입력 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

예제 출력 2

6
6
1
1
1
1
1
1
1

예제 입력 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

예제 출력 3

160
20
8
7
2
1
1
1
1
1

예제 입력 4

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

예제 출력 4

0
538184948
693625420
932738155
251798971

점수

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.