10935: 你猜D

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

我们定义一个数列F(n)代表n的有序拆分数:

比如

3=3                 

     3=1+2              

     3=2+1             

     3=1+1+1

3的有序拆分数为4种。

再比如

     4=4

     4=1+3

     4=3+1

     4=2+2

     4=1+1+2

     4=1+2+1

     4=2+1+1

     4=1+1+1+1

4的有序拆分数有8种,当然我们很容易发现F(n)=2^(n-1),所以咱们的题目肯定不可能是这么简单的。现在我想问的是,给定任意两个数nk,求n的所有拆分情况中,k出现的次数是多少。

Input

输入文件包含多组测试数据。第一行,给出一个整数 TT<=20),为数据组数。

接下来有一行,分别输入两个数n,k1<=n,k<=10^9

Output

输出结果并对1e9+7取余

Sample Input Copy

2
4 2
5 5

Sample Output Copy

5
1

HINT

n=4的拆分数的情况上面给出了,2出现的次数显而易见为5次

n=5的拆分数更多,但是5出现的次数显然只有5=5这一种情况里面会出现,所以输出1.