There is an $n \times m$ grid, and you wish to cover the entire grid using numbered triominoes (the types of polyominoes used in Tetris, specifically the $3$-cell straight bar or the L-shape). These triominoes must be numbered from $1$ to $nm/3$. Additionally, if two triominoes $X$ and $Y$ are such that any cell in $X$ is immediately to the left of or immediately above any cell in $Y$, then the number assigned to $X$ must be less than the number assigned to $Y$.

You need to output the number of such (numbered) covering schemes, modulo $10^9+7$. There are multiple test cases.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Each of the next $T$ lines contains two positive integers $n$ and $m$.

Output

For each test case, output the answer on a single line.

Examples

Input 1

3
1 2
3 4
9 10

Output 1

0
12
983018242

Note

For the second test case in the example, all possible schemes are shown in the image below:

All possible schemes for the second test case.

Constraints

For all test cases, $T \le 10$, $n, m \le 10^4$.

Subtask 1 (10 pts): $n, m \le 4$.

Subtask 2 (30 pts): $n \le 4$, $m \le 100$.

Subtask 3 (20 pts): $n, m \le 100$.

Subtask 4 (40 pts): No additional constraints.