对于给定的整数 $$$n$$$ 和 $$$m$$$,如果满足以下条件,我们称一对整数数组 $$$a$$$ 和 $$$b$$$ 为好:
- $$$a$$$ 和 $$$b$$$ 具有相同的长度,令它们的长度为 $$$k$$$。
- $$$k \ge 2$$$ 和 $$$a_1 = 0,a_k = n,b_1 = 0,b_k = m$$$。
- 对于每个 $$$1 < 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|$$$ 之和。由于答案可能非常大,因此输出它对 $$$10^9 + 7$$$ 取模。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 所有好的数组对 $$$(a,b)$$$ 模 $$$10^9 + 7$$$ 的 $$$|a|$$$ 之和。
示例
输入 #1
4 1 1 1 2 2 2 100 100
输出 #1
8 26 101 886336572
注意
在第一个测试用例中,好的数组对是
- $$$([0, 1], [0, 1])$$$,长度 = $$$2$$$。
- $$$([0, 1, 1], [0, 0, 1])$$$,长度 = $$$3$$$。
- $$$([0, 0, 1], [0, 1, 1])$$$,长度 = $$$3$$$。
因此,长度之和将为 $$${2 + 3 + 3} = 8$$$。