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),所以咱们的题目肯定不可能是这么简单的。现在我想问的是,给定任意两个数n和k,求n的所有拆分情况中,k出现的次数是多少。
Input
输入文件包含多组测试数据。第一行,给出一个整数 T(T<=20),为数据组数。
接下来有一行,分别输入两个数n,k(1<=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.