Lovely 139

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

对于一个下标从 $1$ 开始的 01 串 $S$，若区间 $[l,r]$ 同时满足：

• 当 $l\ne 1$ 时，$S_{l-1}\ne S_l$；
• 当 $r\ne |S|$ 时，$S_{r+1}\ne S_r$；
• 对所有 $l\le i<r$，均有 $S_i=S_{i+1}$；

则称 $[l,r]$ 为 $S$ 的一个极长颜色段。记 $g(S)$ 为 $S$ 的极长颜色段数。例如，$g(00)=1$，$g(1110)=2$，$g(001011)=4$。

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

你需要回答 $T$ 次询问。每次给定 $n,m$，输出 $f(n,m)$ 对 $10^9+7$ 取模的结果。

当 $n=m=0$ 时，唯一的字符串为空串，其极长颜色段数为 $0$。

输入格式

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

接下来 $T$ 行，每行两个非负整数 $n,m$。

输出格式

输出 $T$ 行，第 $i$ 行为第 $i$ 次询问的答案。

样例输入 1

3
2 2
4 6
7 8

样例输出 1

18
1218
54483

样例输入 2

3
845 826
672 826
618 925

样例输出 2

789284214
588160420
730993180

样例输入 3

1
1 46

样例输出 3

139

数据范围

对于全部数据：

• $1\le T\le 10^6$；
• $0\le n,m\le 2\times 10^6$；
• $0\le n+m\le 2\times 10^6$。

子任务

本题按用户明确授权不设置部分分；下列单一满分子任务内的测试点独立计分。

提示

对于第一组样例中的 $n=m=2$，六个字符串的段数之和为 $2+4+3+3+4+2=18$。