E. 密码学2

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

这个密码一定非常安全……但愿吧。

你是南京工程学院数理学院密码学专业的一名硕士研究生。导师的实验室近期遭受攻击，需要你设计一批无懈可击的临时密码来预防后续入侵。

给出两个正整数 $n, m$。构造长度为 $n + m$ 的字符串 $s$，满足：

$\quad$ 1. $s$ 中字符 `0` 恰出现 $n$ 次，字符 `1` 恰出现 $m$ 次；

$\quad$ 2. $\forall i \in [1, n+m-1]$，有 $s_i \neq s_{i+1}$。

求所有合法字符串的个数，答案对 $10^9+7$ 取模。

第一行一个整数 $T$（$1 \le T \le 10^5$）。

接下来 $T$ 行，每行两个正整数 $n, m$（$1 \le n, m \le 10^{18}$），用空格分隔。

$T$ 行，每行一个整数，表示合法字符串个数对 $10^9+7$ 取模。