P13525 [KOI 2025 #2] 新的情缘

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

$N$ 对已经分手的伴侣为了寻找新的情缘而聚集在一起。每对伴侣由 1 名男性和 1 名女性组成，这 $N$ 对伴侣总共由 $N$ 名不同的男性和 $N$ 名不同的女性构成。他们分别坐在编号从 1 到 $2N$ 的 $2N$ 张椅子上，并满足以下条件。 * 没有两个人坐在同一张椅子上。也就是说，每张椅子上恰好只坐了 1 个人。 * 第 $i$ 对分手的伴侣中，男性坐在 $L_i$ 号椅子上，女性坐在 $R_i$ 号椅子上。($1 \le i \le N$) * $1 \le L_i < R_i \le 2N(1 \le i \le N)$ * 不存在满足 $L_i < L_j < R_i < R_j$ 的情况。($1 \le i, j \le N$) 他们计划组成 $N$ 对满足以下条件的新伴侣。 * 新伴侣必须由 1 名男性和 1 名女性组成，并且每个人都必须恰好属于 1 对新伴侣。 * 每个人都必须与不是自己原配的人配对。 * 对于任意一对新伴侣，如果男性所坐椅子的编号为 $l$，女性所坐椅子的编号为 $r$，则必须满足 $l < r$。 例如，我们来考虑 $N=3$ 且 $L_1=1, R_1=6, L_2=2, R_2=3, L_3=4, R_3=5$ 的情况。坐在 1 号椅子的男性和坐在 6 号椅子的女性是已经分手的伴侣，因此不能成为新伴侣。坐在 4 号椅子的男性和坐在 3 号椅子的女性虽然不是分手的伴侣，但由于男性所坐椅子的编号更大，因此也不能成为新伴侣。 反之，坐在 1 号椅子的男性和坐在 3 号椅子的女性可以成为新伴侣。坐在 2 号椅子的男性和坐在 5 号椅子的女性，以及坐在 4 号椅子的男性和坐在 6 号椅子的女性，也都可以成为新伴侣。通过这种方式，可以组成满足条件的 3 对新伴侣。 你需要计算组成 $N$ 对新伴侣的不同方法的总数。两种组成 $N$ 对新伴侣的方法被认为是不同的，是指存在一对新伴侣，它只在其中一种方法中出现。 对于上面给出的例子，可以证明组成 3 对伴侣的方法是唯一的。因此，这种情况的答案是 1。 方法的数量可能非常大，请输出其对 $10^9 + 7$ 取模后的余数。 在一次输入中，你需要解决 $T$ 个测试用例。

第一行给定测试用例的数量 $T$。 从第二行开始，依次是 $T$ 个测试用例。每个测试用例由 $N+1$ 行组成。 每个测试用例的第一行给定 $N$。 对于每个测试用例，接下来的 $N$ 行中的第 $i$ 行 ($1 \le i \le N$) 给定 $L_i$ 和 $R_i$，以空格分隔。

对于每个测试用例，输出一行答案。

### 限制条件 * 所有给定的数都是整数。 * $1 \le T \le 100$ * $1 \le N \le 3\,000$ * 如果将所有测试用例的 $N$ 的总和记为 $S$，则 $1 \le S \le 3\,000$。 * $1 \le L_i < R_i \le 2N(1 \le i \le N)$ * $L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N$ 互不相同。 * 不存在满足 $L_i < L_j < R_i < R_j$ 的情况。($1 \le i, j \le N$) ### 子任务 1. (11 分) $N \le 8, S \le 800$。 2. (32 分) $N \le 16, S \le 1\,600$。 3. (20 分) $N \le 100, S \le 2\,000$，且不存在满足 $L_i < L_j < R_j < L_k < R_k < R_i$ 的情况 ($1 \le i, j, k \le N$)。 4. (27 分) $N \le 100, S \le 2\,000$。 5. (10 分) 无额外限制条件。