5478: D-Link with Balls
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
There were a lot of balls in the factory of Ball Illusion
Technology(BIT). link, a boy, went there to get some balls, but
suddenly, he found that there were too many ways to get balls.
There are 2n buckets in the factory. link may get kx balls from the 2x−1th bucket, where k is a non-negtive integer. He may also get at most x balls from the 2xth bucket.
link wanted to get m balls, and he wondered how many ways there were to take out exactly m balls. While link is calculating the answer, he wants you to calculate it as well, and you should output the answer modulo 109+7.
There are 2n buckets in the factory. li
li
输入
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤105) -- the number of test cases.
Each test case contains two integers n and m(1≤n,m≤106).
The first line contains an integer T (1≤T≤105) -- the number of test cases.
Each test case contains two integers n and m(1≤n,m≤106).
输出
For each test case, print the answer modulo 109+7 in a single line.
样例输入 复制
4
1 1
2 2
3 3
1000000 1000000样例输出 复制
2
6
20
192151600