说明

我们定义一个数列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)，所以咱们的题目肯定不可能是这么简单的。现在我想问的是，给定任意两个数n和k，求n的所有拆分情况中，k出现的次数是多少。

输入格式

输入文件包含多组测试数据。第一行，给出一个整数 T（T<=20），为数据组数。

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

输出格式

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

2
4 2
5 5

5
1

提示

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

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

来源

输入输出练习