我们定义一个数列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取余