# [Solution] Twos and Zeros solution codechef

Twos and Zeros solution codechef – 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.

## [Solution] Twos and Zeros solution codechef

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.

## [Solution] Twos and Zeros solution codechef

• 1 \leq T \leq 10^3
• 1 \leq N, M \leq 10^9

### Sample 1:

Input

Output

2
1 1
2 2

1
5


## [Solution] Twos and Zeros solution codechef Explanation:

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 2s and two 0s) and the second type can be formed in only 1 way. So, the answer is 5.