HP is standing at a distance of X kilometres from her house . She can travel at most K kilometres in a single step. She wants to know total number of ways to reach her house . As the number of ways can be large , print it modulo $10^9+7$.

Note : She can't take step of 0 kilometres, i.e., step should be $positive$ integer.

Input :

First line contains one integers T denoting number of test cases .

Each of the next T lines contains two integers X and K.

Output :
For each test case, print the number of ways modulo $10^9+7$. Answer for each test case should come in a new line.

Constraints :

$1 \le T \le10^5$

$1 \le X \le10^4$

$1 \le K \le 10^2$