Irena and Sirup are organizing their engagement party next weekend. They want to invite almost everybody. They have just bought a very big round table for this occasion. But they are now wondering how should they distribute people around the table. Irena claimed that when there are more than K women next to each other, this group will chat together for the whole night and won’t talk to anybody else. Sirup had no other choice but to agree with her. However, being a mathematician, he quickly became fascinated by all the possible patterns of men and women around the table. Problem specification There will be N people sitting at the round table. Some of them will be men and the rest will be women. Your task is to count in how many ways it is possible to assign the places to men and women in such a way that there will not be more than K women sitting next to each other. If one assignment can be made from another one by rotating all the people around the table, we consider them equal (and thus count this assignment only once).

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line. The input for each test case consists of a single line that contains the two integers N and K. K < = 2000 N < = 2000

For each test case output a single line with one integer – the number of ways how to distribute people around the table, modulo 100000007.

In the first test case there are two possibilities: MMM or MMW (M is a man, W is a woman). In the second test case there are two more possibilities: MWW and WWW. In the third test case the three possibilities are: MMMM, MMMW, and MWMW.

IPSC 2008