列表生成

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定整数 $n,m$。若整数数组 $a,b$ 满足以下条件，则称数组对 $(a,b)$ 是好的：

• $a,b$ 的长度相同，记为 $k$；
• $k\ge2$，$a_1=0,a_k=n,b_1=0,b_k=m$；
• 对每个 $1<i\le k$，均有 $a_i\ge a_{i-1}$、$b_i\ge b_{i-1}$，并且 $a_i+b_i\ne a_{i-1}+b_{i-1}$。

请计算所有好数组对 $(a,b)$ 的长度 $k$ 之和，并对 $10^9+7$ 取模。

输入格式

第一行一个整数 $t$，表示测试数据组数。

随后每组数据一行两个整数 $n,m$。

输出格式

对每组数据输出一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例输入

4
1 1
1 2
2 2
100 100

样例输出

8
26
101
886336572

数据范围

$1\le t\le10^4$，$1\le n,m\le5\cdot10^6$。所有测试数据中 $n$ 之和不超过 $5\cdot10^6$，$m$ 之和不超过 $5\cdot10^6$。

说明

当 $n=m=1$ 时，三个好数组对的长度分别为 $2,3,3$，答案为 $8$。