Faizal and Sultan are having a one-on-one faceoff. Before stepping into the fight, each of them smoked a special kind of weed from Jhalwa. Smoking k grams of this weed grants the smoker the ability to resurrect k times after dying. Sultan smoked M grams of this weed, and Faizal smoked N grams.

However, Faizal was addicted to this kind of weed since his childhood, and so developed a side effect: if Faizal dies and is resurrected, he temporarily loses his ability to resurrect; and only gains it back after killing Sultan at least once (given that he hasn't resurrected N times already). Sultan has no such restriction.

The fight ends whenever one of the two is killed without being able to resurrect. In other words, either Sultan is killed M+1 times, or Faizal is killed N+1 times, or Faizal is killed twice in a row.

Any possible fight can be described by the sequence of deaths - for example, with N = 2 and M = 2, the string FSSFS encodes the fight where:
1. First, Sultan kills Faizal. Faizal resurrects, and temporarily loses his ability to resurrect.
2. Then, Faizal kills Sultan. Sultan resurrects, and Faizal's resurrection is now active.
3. Faizal kills Sultan again. Sultan resurrects.
4. Sultan kills Faizal, who resurrects. Now Sultan has no more chances to revive.
5. Faizal kills Sultan, who stays dead; and the fight ends.

Faizal's wife Mohsina is getting anxious about the fight and asks for your help in finding the number of different ways the fight between Faizal and Sultan can end up happening. Because this value can be quite large, compute it modulo 10^{9} + 7.

Two fights are considered different if and only if the sequence of deaths corresponding to those fights are different. For example, the sequence SF is different from the sequence FS and hence these represent different fights.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, containing two space-separated integers N and M.

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

For each test case, output a single line containing the answer - the possible number of fights between Faizal and Sultan, modulo 10^{9} + 7.

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

$1 ≤ T ≤ 2000$
$0 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 10^{5}$
- Sum of $N$ over all test cases will not exceed $10^{6}$
- Sum of $M$ over all test cases will not exceed $10^{6}$

----- Sample Input 1 ------ 
3
2 1
12 6
6969 8563
----- Sample Output 1 ------ 
7
255
988402422

----- explanation 1 ------ 
Test Case 1: The death sequences corresponding to the $7$ possible fights are:
- SS
- SFS
- FSS
- FSFS
- FF
- SFF
- FSFF

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Combinatorics

Mathematics


Solutions:
import sys
input = sys.stdin.readline

def il():
	return list(map(int, input().split()))

def ii():
	return int(input())

def imi():
	return map(int, input().split())

def ist():
	return input()
p = 10 ** 9 + 7

def power(x, y, m):
	if y == 0:
		return 1
	if x == 1:
		return 1
	a = power(x, y // 2, m) % m
	a = a * a % m
	if y % 2 == 0:
		return a
	else:
		return x * a % m

def mmi(a, m):
	return power(a, m - 2, m)
mi = [0] * (10 ** 5 + 7)
for i in range(1, 10 ** 5 + 5):
	mi[i] = mmi(i, p)

def solve(n, m):
	a = 1
	s = 1
	for i in range(1, n + 2):
		a = a * (m + 2 - i) * mi[i] % p
		s = (s + a) % p
	return (s, a)
t = ii()
for _ in range(t):
	(n, m) = imi()
	if n > m:
		print((power(2, m + 2, p) + p - 1) % p)
	else:
		(s, x) = solve(n, m)
		print((2 * s - 1 - x + p) % p)