Summing Maximum Color Segments

Given a binary string $S$ consisting of characters (0) and (1) with indices starting from 1, we define an interval ([l,r]) to be an extremely long color segment if and only if it satisfies all the following conditions:

1. If (l \neq 1), then (S_{l-1} \neq S_l).
2. If (r \neq |S|), then (S_{r+1} \neq S_r).
3. For all (i \in [l, r)), (S_i = S_{i+1}).

In other words, an extremely long color segment is exactly a maximal contiguous block of identical characters in (S).

Define (g(S)) to be the number of different extremely long color segments in (S). For example, (g(00)=1), (g(1110)=2), and (g(001011)=4).

Now, let (f(n, m)) be the sum of (g(S)) over all binary strings (S) that contain exactly (n) zeros and (m) ones. You are given (T) queries. For each query, you are given two integers (n) and (m), and you need to compute (f(n, m) \bmod (10^9+7)).

Important Note: When either (n=0) or (m=0), there is only one possible string consisting of all identical characters, and its number of segments is 1.

Hint on the approach: Let the total number of valid binary strings be (T = \binom{n+m}{n}). Note that every valid string has at least one contiguous block (its first character) and every time a change happens between consecutive positions a new block is started. Thus, (g(S)=1+\text{(number of transitions)}). Through combinatorial reasoning, one can show that for (n,m \ge 1): [ f(n, m) = \binom{n+m}{n} + 2,(n+m-1),\binom{n+m-2}{n-1} \pmod{10^9+7}. ]

Your task is to answer (T) queries efficiently.

inputFormat

The first line contains an integer (T) (the number of test cases). Each of the following (T) lines contains two integers (n) and (m), denoting the numbers of zeros and ones respectively.

outputFormat

For each test case, output a single line with (f(n, m) \bmod (10^9+7)).

sample

3
1 1
0 2
2 2

4
1
18