配水方案

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

    SnowACM队里的小朋友,但他思维敏捷,让fishhead十分赏识,于是会经常让他帮忙解决一些问题。一天,fishhead做一份项目时遇到了问题。如上图所示,为水流运送模型,最底层为最终用户。最高点为总水量。每一个节点向下分配水的时候可以随意选择给左边多少,给右边多少,但一定要分配完。且最终用户收到的水量至少为1.现在告诉你总共的水量和最终用户的数量。问有多少种不同的构造配水方案。

Input

第一行为整数t,代表t组测试数据 下面的t行分别有两个正整数sum和n,分别代表总水量和最终用户数量.且sum < 1,000,000;n < 1,000,000

Output

每一个测试数据给出一个整数,为配水方案个数ans.因为最后的结果很大,所以请对输出结果ans%1,000,000,007

Sample Input

5
5  3
16  5
15  4
31556  15
500  150

Sample Output

2
1
24
81126713
0

Hint

Source

StSky

提交代码