The Academy is a school where each common area is laid out on an $m\times n$ grid and each cell in the grid is $\mbox{1}$ meter by $\mbox{1}$ meter. Danielle is their new head of security, and she wants to place a surveillance camera along every square meter of each common area. Because the school doesn't have enough money in their security budget to do this, she decides to further restrict camera placement according to the following rules:

Each cell can contain at most $\mbox{1}$ camera.
Every $3\times3$ subgrid of a common area must have exactly $2$ cameras.

Given the values of $m$ and $n$ for $\textbf{c}$ common areas, determine the number of ways Danielle can install cameras in each common area according to the rules above. Then, for each common area, print the number of ways she can install these cameras on a new line. As these values may be quite large, your answer must be modulo $10^9+7$.

Input Format

The first line contains an integer, $\textbf{c}$, denoting the number of common areas to install cameras in.

Each line $\boldsymbol{i}$ of the $\textbf{c}$ subsequent lines contains two space-separated integers describing the respective values of $m$ and $n$ for a common area's grid.

Constraints

For $20\%$ of the maximum score:

$1\leq c\leq10$
$3\leq m,n\leq15$

For $50\%$ of the maximum score:

$1\leq c\leq100$
$3\leq m,n\leq50$

For $100\%$ of the maximum score:

$1\leq c\leq10^5$
$3\leq m,n\leq1000$

Output Format

For each common area, print an integer denoting the number of ways Danielle can install the cameras according to the given rules, modulo $10^9+7$, on a new line.

Sample Input 0
2
3 3
3 4

Sample Output 0
36
78

Explanation 0

The diagram below depicts the number of ways to place cameras in a $3\times4$ grid:

As there are $78$ ways to place cameras in this common area, we print the result of $78~\text{mod}~(10^9+7)=78$ on a new line.

见题面

见题面