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\)