题目描述

题目译自 USACO 2024 December Contest, Platinum Problem 3. Maximize Minimum Difference

哞！你被给定了一个整数 $N$（$2 \le N \le 2000$）。考虑 $[0, 1, 2, \dots, N-1]$ 的所有排列 $p = [p_0, p_1, \dots, p_{N-1}]$。令 [ f(p) = \min_{i=0}^{N-2} |p_i - p_{i+1}| ] 表示 $p$ 中任意两个连续元素之间的最小绝对差值，并令 $S$ 表示所有达到 $f(p)$ 最大可能值的 $p$ 的集合。

你还被给定了 $K$（$0 \le K \le N$）个限制，形式为 $p_i = j$（$0 \le i, j < N$）。计算 $S$ 中满足所有限制的排列数量，对 $10^9+7$ 取模。

---

输入格式

输入的第一行包含 $T$ 和 $N$（$1 \le TN \le 2 \cdot 10^4$），表示你需要求解 $T$ 个独立的测试用例，每个测试用例指定一组不同的限制。
每个测试用例的第一行包含 $K$，以下 $K$ 行，每行包含 $i$ 和 $j$。输入保证：

• 相同的 $i$ 在同一测试用例中不会出现超过一次。
• 相同的 $j$ 在同一测试用例中不会出现超过一次。

---

输出格式

对于每个测试用例输出一行，包含答案模 $10^9+7$ 的余数。

---

样例 1

输入

3 4
0
1
1 1
2
0 2
2 3

输出

2
0
1

$f(p)$ 的最大值为 $2$，且 $S = \{[2,0,3,1], [1,3,0,2]\}$。

---

样例 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

输出

6
6
1
1
1
1
1
1
1

$p = [5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ 在所有测试用例中都应当被计算在内。

---

样例 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

输出

160
20
8
7
2
1
1
1
1
1

$p = [4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ 在所有测试用例中都应当被计算在内。

---

样例 4

输入

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

输出

0
538184948
693625420
932738155
251798971

确保输出答案对 $10^9+7$ 取模。

---

数据范围与提示

• 测试点 $5$：$N = 15$。
• 测试点 $6$：$N = 2000$。
• 测试点 $7$-$9$：对于所有测试用例，均存在限制 $p_0 = \lfloor N/2 \rfloor$。
• 测试点 $10$-$13$：对于所有测试用例，均存在某个限制 $p_i = j$，其中 $j$ 等于 $\lfloor N/2 \rfloor$。
• 测试点 $14$-$20$：没有额外限制。