题目描述

给定一个包含 $L\times N$ 个点的简单无向图。

顶点用 $(i,j)$ 标号，其中：

图中的边按如下规则确定：

1. 对于所有 $i\in[1,L)$，$j\in[1,N]$，$(i,j)$ 与 $(i+1,j)$ 之间有边。

2. 对于所有 $i\in[1,L]$，$j,k\in[1,N]$，且 $j\ne k$，$(i,j)$ 与 $(i,k)$ 之间有边。

也就是说：

• 相邻两层中，相同编号的点之间有边；
• 同一层内的任意两个不同点之间有边。

请计算这张图的哈密顿回路数。

哈密顿回路是指一个顶点集合的排列 $P$，满足：

• $P_1=(1,1)$；
• 对于所有 $i\in[1,|V|-1]$，$P_i$ 与 $P_{i+1}$ 之间有边；
• $P_{|V|}$ 与 $P_1$ 之间有边。

答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行两个整数 $N,L$，含义如题目描述所述。

输出格式

对于每组数据，输出一行一个整数，表示哈密顿回路数对 $10^9+7$ 取模后的结果。

样例输入

9
3 2
2 3
4 2
3 3
4 4
6 3
50 50
19 49
500 9215

样例输出

6
2
60
12
2652
3516720
637478082
837916483
124848471

数据范围与子任务

对于除了样例外的所有数据，满足：

子任务如下：

提示

请注意实现常数的影响。可以使用 64 位或 128 位整数来减少取模操作次数。