Well its now time for some serious task . There are lots of beads available and in two colours , namely white and black . So there are many beads of both the colours . One has to make a string of beads by joining beads with end to end . But there are some constraint , and you have to follow that constraint. While making beads , you have to make sure that there should not be K beads of black colour consecutively and also there should not be any bead string which has black bead in front ,i.e it must have white bead  in front . So the task is quite simple , find all possible ways of making a string of bead of length N which satisfies the above constraint .

Input:

The first line of the input contains an integer T denoting the number of test cases. The descriptionof T test cases follows.

Output:

Next T lines contains 2 integers N and K.

Print a line for each test case containing the required answer modulo 1000000007.

Constraints :

1<=T<=1000000

1<=N<=10000

1<=K<=100

Sample Input :
3
2 3
2 1
3 4
2
1
4
Explanation :
For Sample test case 1 , N=2 and K=3 , so as 3 beads of black colour should not present we have white-white , white-black.
Note black-white is not the valid one so in this case the answer is 2.