SP19545 BWB - Black and White beads

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

N/A

N/A