哞！给定一个整数 $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}|$ 表示排列中任意两个相邻元素之差的绝对值的最小值，并令 $S$ 为所有使得 $f(p)$ 达到最大值的排列 $p$ 构成的集合。

此外，给定 $K$ ($0\le K\le N$) 个形如 $p_i=j$ ($0\le i, j < N$) 的约束。请计算满足所有约束的 $S$ 中的排列数量，结果对 $10^9+7$ 取模。

输入格式

第一行包含 $T$ ($1\le TN\le 2\cdot 10^4$) 和 $N$，表示你需要解决 $T$ 个独立的测试用例，每个测试用例由一组不同的约束指定。

每个测试用例以 $K$ 开头，随后是 $K$ 行，每行包含 $i$ 和 $j$。保证：

• 同一个测试用例中，同一个 $i$ 不会出现多次。
• 同一个测试用例中，同一个 $j$ 不会出现多次。

输出格式

对于每个测试用例，输出一行，表示满足条件的排列数量对 $10^9+7$ 取模的结果。

样例

样例输入 1

3 4
0
1
1 1
2
0 2
2 3

样例输出 1

2
0
1

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

样例输出 2

6
6
1
1
1
1
1
1
1

样例说明 2

$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

样例输出 3

160
20
8
7
2
1
1
1
1
1

样例说明 3

$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

样例输出 4

0
538184948
693625420
932738155
251798971

样例说明 4

请确保输出结果对 $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