조화로운 직사각형

꼭짓점 네 개가 모두 색으로 칠해진 직사각형을 색칠된 직사각형이라고 한다. 색칠된 직사각형은 같은 색을 가진 인접한 꼭짓점 두 개가 있고, 나머지 두 꼭짓점도 서로 같은 색이면 조화롭다. 예를 들어 $\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}\}$에 속한 각 점을 빨강, 파랑, 노랑 중 하나의 색으로 칠한다. 코토리는 변이 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}$ 두 칠하는 방법은 어떤 점의 색이 하나라도 다르면 서로 다른 방법이다. 답은 $10^9 + 7$로 나눈 나머지로 구한다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^4$)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 $n$, $m$ ($1 \le n, m \le 2 \times 10^3$)이 주어진다.

각 테스트 케이스마다 칠하는 방법의 수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.