题目描述

A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other.

For example, $\begin{bmatrix} 1 & 0\\ 1 & 0 \end{bmatrix}$, $\begin{bmatrix} 0 & 0\\ 1 & 1 \end{bmatrix}$ and $\begin{bmatrix} 1 & 1\\ 1 & 1 \end{bmatrix}$ are harmonious, while $\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}$ is not (same number for same color, and different numbers for different colors).

For each point in $\{(x,y) | 1 \le x \le n, 1 \le y \le m, x,y \in \mathbb{Z}\}$, where $\mathbb{Z}$ is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the $x$- or $y$-axis. That is to say, there exists $1 \le x_1 < x_2 \le n$ and $1 \le y_1 < y_2 \le m$ such that

$$\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} $$

or

$$\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} $$

where $\text{color}(x, y)$ is the color of point $(x, y)$.

Two coloring plans are considered different if there exists a point having different colors in the two coloring plans.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first and only line contains three integers $n$, $m$($1 \le n, m \le 2 \times 10^3$).

输出格式

For each test case output one line containing one integer indicating the number of different ways of coloring modulo $(10^9 + 7)$.

题目大意

题目描述

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

例如，矩阵 $\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)$。

3
1 4
2 2
3 3

0
15
16485