[Solution] Twos and Zeros CodeChef Solution

Problem

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$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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