题目描述

一个顶点着色的矩形是指四个顶点都被涂上颜色的矩形。对于一个顶点着色的矩形来说，如果我们可以找到两个相邻顶点的颜色相同，而另外两个顶点也互相颜色相同，则称这个矩形是和谐的。

例如，矩阵 $\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) | 1 \le x \le n, 1 \le y \le m, x,y \in \mathbb{Z}\}$，其中 $\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)$。