Problem 3. Maximize Minimum Difference

USACO 2024 December Contest, Platinum

注意：本题的时间限制为 4 秒，通常限制的 2 倍。

哞！你被给定了一个整数 $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$ 的余数。

输入样例：

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]\}$。

输入样例：

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]$ 在所有测试用例中都应当被计算在内。

输入样例：

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]$ 在所有测试用例中都应当被计算在内。

输入样例：

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：没有额外限制。

供题：Benjamin Qi