Dexter and Mandark are playing a game. The game consists of N rounds. After each round, the winner (either Dexter or Mandark) will be awarded one point. The player with more points at the end of the game wins.
Mandark is Dexter's arch enemy. Dexter wants to prove that he is superior to Mandark.
He wants that after each round in the game he has atleast M times the points that Mandark has.
Dexter is busy planning his game strategy so he asks you to tell him the number of ways he can win the game with the condition just described.
Two ways of winning the game are said to be different if some round is won by a different person.
Input:
The first line contains T, the number of test cases.
Each test case consists of a single line with two space separated integers N and M.
Output:
For each test case, output the answer modulo 10^9 + 7
Constraints:
1<=T<=10
1<=M<=N<=1000
For the first test case, the possible sequence of winners of rounds are: DDD DMD DDM
( MDD is not possible because in that sequence, even though Dexter wins in the end, but after first round Dexter does not have atleast M times the points that Mandark has)
For the second test case, the only possible sequence is : DDD
[D=Dexter, M=Mandark]
