P11655 「FAOI-R5」Lovely 139

$\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(00)=1$，$g(1110)=2$，$g(001011)=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 解释 对于第一组数据 $n=2,m=2$，一共有六个本质不同的 $S$，答案为 $g(0011)+g(0101)+g(0110)+g(1001)+g(1010)+g(1100)=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 4 \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$。