← Home
write a go solution for Description:
For given integers n and m, let's call a pair of arrays a and b of integers good, if they satisfy the following conditions:

- a and b have the same length, let their length be k.
- k>=2 and a_1=0,a_k=n,b_1=0,b_k=m.
- For each 1<i<=k the following holds: a_i>=a_i-1, b_i>=b_i-1, and a_i+b_ineqa_i-1+b_i-1.

Find the sum of |a| over all good pairs of arrays (a,b). Since the answer can be very large, output it modulo 10^9+7.

Input Format:
The input consists of multiple test cases. The first line contains a single integer t(1<=t<=10^4)  — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers n and m (1<=n,m<=5*10^6).

It is guaranteed that the sum of n over all test cases does not exceed 5*10^6 and the sum of m over all test cases does not exceed 5*10^6.

Output Format:
For each test case, output a single integer  — the sum of |a| over all good pairs of arrays (a,b) modulo 10^9+7.

Note:
In the first testcase, the good pairs of arrays are

- ([0,1],[0,1]), length = 2.
- ([0,1,1],[0,0,1]), length = 3.
- ([0,0,1],[0,1,1]), length = 3.

Hence the sum of the lengths would be 2+3+3=8.. Output only the code with no comments, explanation, or additional text.