Problem E: 2017NHOI初中 第五题 取值

Problem E: 2017NHOI初中 第五题 取值

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MB

Description

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

Input

第一行为一个正整数 T,表示数据组数。
接下来 T 行,每行两个正整数,分别为 m 和 n。

Output

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

Sample Input Copy

2
3 2
7 3

Sample Output Copy

2
8

HINT

【数据规模】
对于 10%的数据,1<=n<=m<=10
对于 30%的数据,1<=n<=m<=50
对于 50%的数据,1<=n<=m<=100
对于 100%的数据,T<=20,1<=n<=m<=300