Kulyash has given you a bag with (N + M) balls having distinct colours. Among these, N balls have the number 2 printed on them and M balls have the number 0 printed on them.

He defines the score of a non-empty subset S of these (N + M) balls as:
(sum of the balls in S) - (size of S).

Find the count of non-empty subsets of these (N + M) balls having their scores divisible by 3. Since the answer can be huge, output it modulo 10^{9} + 7.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first and only line of each test case contains two space-separated integers N and M — the number balls having 2 and the number of balls having 0 respectively.

------ Output Format ------

For each test case, output on a new line, the number of non-empty subsets having scores divisible by 3, modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 10^{3}$
$0 ≤ N, M ≤ 10^{9}$

----- Sample Input 1 ------
2
1 1
2 2

----- Sample Output 1 ------
1
5

----- explanation 1 ------
Test case $1$: The only non-empty subset having score divisible by $3$ is $[2, 0]$. The score of this subset is $(2 + 0) - (2) = 0$, which is divisible by $3$. So, the answer is $1$.

Test case $2$: There are $2$ types of subsets having scores divisible by $3$: $[2,0]$ and $[2,2,0,0]$. The first type of subset can for formed in $4$ ways (there are two $2$s and two $0$s) and the second type can be formed in only $1$ way. So, the answer is $5$.

见题面

见题面