顶点着色矩形是指四个顶点都被涂上颜色的矩形。对于一个顶点着色矩形，当且仅当我们可以找到两个相邻的顶点颜色相同，且另外两个顶点颜色也相同时，称其为“和谐”的。

例如， $\begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}$，$\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}$ 和 $\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ 是和谐的，而 $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$ 则不是（相同的数字代表相同的颜色，不同的数字代表不同的颜色）。

对于集合 $\{(x, y) \mid 1 \le x \le n, 1 \le y \le m, x, y \in \mathbb{Z}\}$ 中的每个点，Kotori 想要将其涂成三种颜色之一：红色、蓝色或黄色。她想知道有多少种不同的涂色方案，使得存在至少一个由这些点组成的、边平行于 $x$ 轴或 $y$ 轴的和谐矩形。也就是说，存在 $1 \le x_1 < x_2 \le n$ 和 $1 \le y_1 < y_2 \le m$ 使得：

$$\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_1, y_2) \\ \text{color}(x_2, y_1) = \text{color}(x_2, y_2) \end{cases}$$

或者

$$\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_2, y_1) \\ \text{color}(x_1, y_2) = \text{color}(x_2, y_2) \end{cases}$$

其中 $\text{color}(x, y)$ 是点 $(x, y)$ 的颜色。

如果两种涂色方案中存在至少一个点颜色不同，则认为这两种方案是不同的。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n, m$ ($1 \le n, m \le 2 \times 10^3$)。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足条件的涂色方案数，结果对 $(10^9 + 7)$ 取模。

样例

输入格式 1

3
1 4
2 2
3 3

输出格式 1

0
15
16485