P11460 [USACO24DEC] Maximize Minimum Difference P

**注意：本题的时间限制为 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

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

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

样例 1 解释： $f(p)$ 的最大值为 $2$，且 $S=\{[2,0,3,1], [1,3,0,2]\}$。 样例 2 解释： $p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ 在所有测试用例中都应当被计算在内。 样例 3 解释： $p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ 在所有测试用例中都应当被计算在内。 样例 4 解释： 确保输出答案对 $10^9+7$ 取模。 - 测试点 $5$：$N=15$。 - 测试点 $6$：$N=2000$。 - 测试点 $7\sim 9$：对于所有测试用例，均存在限制 $p_0=\lfloor N/2\rfloor$。 - 测试点 $10\sim 13$：对于所有测试用例，均存在某个限制 $p_i = j$，其中 $j$ 等于 $\lfloor N/2\rfloor$。 - 测试点 $14\sim 20$：没有额外限制。