As Ash started his quest of collecting all the pokemon, he came across an old sage sitting in the shade of a banyan tree. He asked the old wise man about the presence of pokemon in that area. As it turned out, the old sage was a pokemon master in his days and had infinite collection of pokemon with himself. Realizing his opportunity, Ash asked the old wise sage to help him in his quest. Much to Ash’s joy, he agreed, but on a condition. Ash had to answer one question. He was ready to give him n pokemon of k different types. The question he asked Ash was, ‘How many different ways are there for Ash to select his n pokemon given the condition that he had to have all k different types of pokemon?’ Help Ash in solving the puzzle.

Input

The first line of input contains a number T <= 100 that indicates the number of test cases to follow. Each test case consists of one line containing n and k, where n is the number of pokemon Ash selects and k is the number of different types of pokemon.

Output

For each test case print one line containing the number of possibilities that Ash would have had. If the answer is too large, print it modulo 1000000007.

Constraints

1<=k<=n<=100000