← 返回题目列表

Codeforces · 1747/E

E. 列表生成

中文机器翻译题面 查看原题

对于给定的整数 $$$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$$$。