题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

$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$，以空格分隔。

输出格式

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

5
1
1 2
2
1 4
2 3
3
1 6
2 5
3 4
3
1 6
2 3
4 5
4
1 8
5 6
2 7
3 4

0
1
2
1
6

提示

限制条件

• 所有给定的数都是整数。
• $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 分) 无额外限制条件。