99095 - 取值

现给你两个正整数n, m。请问有多少种对整数 x_1, x_2 ,..., x_n的取值,使得等式 x_1 + x_2 +...+ x_n = m 成立。你的赋值必须满足 0 ≤ x_1 ≤ x_2 ≤ ... ≤ x_n 。例如,当 m = 3, n = 2 时, 共有 2 种取法,分别为 (x1,x2)=(0,3)或(1,2)。请输出答案除以10^8 + 7 的余数。

输入

第一行为一个正整数 T,表示数据组数。

接下来 T 行,每行两个正整数,分别为 m 和 n。

输出

输出 T 行,分别表示对每一组数据的答案除以10^8 + 7 的余数。

样例

输入

2
3 2 
7 3

输出

2
8

提示

【数据规模】

对于 10%的数据,1<=n<=m<=10

对于 30%的数据,1<=n<=m<=50

对于 50%的数据,1<=n<=m<=100

对于 100%的数据,T<=20,1<=n<=m<=300

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题