轮符雨

题号：NC305811
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 加藤翔子得到整数 $n$ 和 $t$ ，她现在考虑所有长度为 $n$ 的二进制字符串（仅含字符 $0$ 和 $1$ ）。把字符串按极大连续同字符段（ $L$ ）分解，设这些 $L$ 的长度依次为 $L_1, L_2, \dots, L_k$ （各 $L_i\ge1$ ，且 $L_1 + L_2 + \dots + L_k = n$ ）。定义该字符串的值 $\mathrm{val}$ 为：
$\displaystyle\mathrm{val} \;=\; \sum\limits_{i=1}^{k} \binom{L_i}{2}<br />\;=\; \sum\limits_{i=1}^{k}\frac{L_i(L_i-1)}{2}.$

$\hspace{15pt}$ 现在加藤翔子想计算满足 $\mathrm{val}=t$ 的二进制字符串数量。不过她没办法快速的做出来，所以你能帮帮她吗？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入两个整数  和 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示满足条件的字符串数量对  取模后的结果。

示例1

输入

复制

2
3 1
4 3

输出

复制

4
4

说明

在第一个样例中，满足  且长度为  的字符串为：、、、。
在第二个样例中，例如字符串 ，按极大连续同字符段（）分解得到 ，则 ；同类字符串还有、、，共  个。

示例2

输入

复制

1
91 78

输出

复制

259448003

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注: