贡献名单

想法	标程	数据	验题	题解
yzq_yzq			xxxxxzy	喵仔牛奶

题目背景

$\text{Height}\leq139$。

题目描述

对于一个 $\tt 01$ 串 $S$（下标从 $1$ 开始），我们定义它的一个区间 $[l,r]$ 是极长颜色段，当且仅当它同时满足以下条件：

• 如果 $l\neq 1$，$S_{l-1}\neq S_l$；
• 如果 $r\neq \lvert S\rvert$，$S_{r+1}\neq S_r$；
• $\forall i\in[l,r),S_i=S_{i+1}$。

定义 $g(S)$ 为 $S$ 的不同极长颜色段数。比如 $g($$\tt00$$)=1$，$g($$\tt1110$$)=2$，$g($$\tt001011$$)=4$。

定义 $f(n,m)$ 的值为所有恰好包含 $\boldsymbol n$ 个 $\tt 0$ 和 $\boldsymbol m$ 个 $\tt 1$ 的 $\tt 01$ 串 $S$ 的 $g(S)$ 之和。

你需要回答 $T$ 个问题，每次给出 $n,m$ 的值，求 $f(n,m)$ 的值对 $10^9+7$ 取模后的结果。

输入格式

第一行输入一个正整数数 $T$，表示问题个数。

接下来 $T$ 行，每行两个非负整数 $n,m$，表示问题的参数。

输出格式

输出 $T$ 行，每行为对应问题的答案。

样例 #1

样例输入 #1

3
2 2
4 6
7 8

样例输出 #1

18
1218
54483

样例 #2

样例输入 #2

3
845 826
672 826
618 925

样例输出 #2

789284214
588160420
730993180

样例 #3

样例输入 #3

1
1 46

样例输出 #3

139

提示

样例 1 解释

对于第一组数据 $n=2,m=2$，一共有六个本质不同的 $S$，答案为 $g($$\tt0011$$)+g($$\tt0101$$)+g($$\tt0110$$)+g($$\tt1001$$)+g($$\tt1010$$)+g($$\tt1100$$)=2+4+3+3+4+2=18$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（15 pts）：$0 \le n+m \le 20$，$1 \le T \le 10$。
• Subtask 2（25 pts）：$0 \le n,m \le 2 \times 10^3$。
• Subtask 3（20 pts）：$1 \le T \le 10$。
• Subtask 4（40 pts）：无特殊限制。

对于所有数据，保证 $1 \leq T \leq 10^6$，$0 \leq n+m\leq 2 \times 10^6$，$0\le n,m\le 2\times10^6$。