Maxwell 正在装修他的浴室，想要重新铺设墙面瓷砖。他的墙面是一个 $2m \times 2n$ 的矩形。为了描述瓷砖在墙上的放置方式，我们使用一个以中心为原点的坐标系，使得墙面由顶点为 $(m, n), (m, -n), (-m, -n)$ 和 $(-m, n)$ 的矩形所描述。例如，当 $m = 3, n = 2$ 时，他的墙面看起来如下所示：

Maxwell 希望使用由 $1 \times 1$ 正方形组成的连通多格骨牌（polyominoes）来铺满他的墙面，但他对瓷砖的放置方式有特殊要求。如果一个瓷砖所包含的所有正方形中心处的 $\max(|x|, |y|)$ 值相等，则称该瓷砖是“放置良好”的（well-placed）。这些瓷砖允许中间有“孔”，只要瓷砖本身是一个连通的整体即可。

例如，上述墙面的一种可能的良好铺设方式如下：

Maxwell 有多少种方式可以用放置良好的瓷砖铺满他的浴室墙面？如果两种铺设方案中，有两个正方形在一种方案中属于同一个瓷砖，而在另一种方案中属于不同的瓷砖，则认为这两种方案是不同的。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例包含一行，包含两个整数 $m$ 和 $n$ ($1 \le m, n \le 10^6$)，即上述描述 Maxwell 墙面尺寸的参数。

注意：所有测试用例中 $n$ 或 $m$ 的总和没有额外限制。

输出格式

对于每个测试用例，输出一个整数，表示 Maxwell 用放置良好的瓷砖铺满墙面的方案数，对 $10^9 + 7$ 取模。

样例

输入 1

4
1 1
3 1
2 3
5 4

输出 1

12
192
3136512
734798461

说明

以下是第一个样例中 12 种可能的铺设方式：