CF1747E.List Generation

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 \ge 2$ and $a_1 = 0, a_k = n, b_1 = 0, b_k = m$.
• For each $1 \lt i \le k$ the following holds: $a_i \geq a_{i - 1}$, $b_i \geq b_{i - 1}$, and $a_i + b_i \neq a_{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$.

对于给定的整数 $n$ 和 $m$，若整数数组对 $(a, b)$ 满足以下条件，则称其为“好”的：

• $a$ 和 $b$ 长度相同，记该长度为 $k$；
• $k \ge 2$，且 $a_1 = 0,\ a_k = n,\ b_1 = 0,\ b_k = m$；
• 对每个 $1 \lt i \le k$，均满足：$a_i \geq a_{i - 1}$，$b_i \geq b_{i - 1}$，且 $a_i + b_i \neq a_{i - 1} + b_{i - 1}$。

求所有“好”的数组对 $(a,b)$ 对应的 $|a|$（即数组 $a$ 的长度 $k$）之和。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

The input consists of multiple test cases. The first line contains a single integer $t (1 \leq t \leq 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 \leq n, m \leq 5 \cdot 10^6)$.

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

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 5 \cdot 10^6$）。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^6$，且所有测试用例中 $m$ 的总和不超过 $5 \cdot 10^6$。

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

对于每个测试用例，输出一个整数——即所有好数组对 $(a,b)$ 对应的 $|a|$ 之和，对 $10^9 + 7$ 取模的结果。

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

在第一个测试用例中，满足条件的数组对有：

• $([0, 1], [0, 1])$，长度为 $2$。
• $([0, 1, 1], [0, 0, 1])$，长度为 $3$。
• $([0, 0, 1], [0, 1, 1])$，长度为 $3$。

因此，这些长度之和为 ${2 + 3 + 3} = 8$。