Type: Default 1000ms 256MiB

密码学2

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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$ 取模。

Input Format

第一行一个整数 $T$($1 \le T \le 10^5$)。

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

Output Format

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

5
1 1
2 1
2 2
1 3
5 7
2
1
2
0
0