Children`s shop#3238
The children's shop received identical cubes. To maintain the diversity of assortment, the shop management decided to make them colorful. It is possible to paint the cubes in different colors, and do not necessarily use all the colors.
Given the numbers and , determine how many coloring options exist (two options are considered different if the number of cubes of at least one color differs).
The first line of the input file contains the number of tests (1 \le t \le 10). Each test consists of a single string containing space-separated and (1 \le n, k \le 10^{18}).
For each test case output the line that contains the answer to the problem. Since the answer may be large enough, output it modulo (10^9+7).
Example 1