In the children's shop brought n identical blocks. To maintain the diversity of assortment management of the shop decided to make them colorful. It is possible to paint the cubes in k different colors, and do not necessarily use all the colors.
Determine the numbers n and k as there are options for coloring (different options are considered, in which different blocks of at least one color).
he first line of the input file contains the number of tests t (1 ≤ t ≤ 10). Each test consists of a single string containing a space of n and k (1 ≤ n, k ≤ 10^18).
For each test case output the line that contains the answer to the problem. Since the answer may be large enough to carry him out modulo 1000000007 (10^9+7).