Children`s shop

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).

Input

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).

Output

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).

Examples