You are standing at a distance of \(X\) kilometers from your house. You can travel at most \(K\) kilometers in a single step.

Your task is to determine the total number of ways to reach your house.
As the number of ways can be large, print it modulo \(10^9+7\).

Note: You cannot take a step of \(0\) kilometers. This means that the steps should be \(positive\) integers.

Input format

• First line: An integer \(T\) denoting the number of test cases
• Each of the next \(T\) lines: contains two integers \(X\) and \(K\)

Output format
For each test case, print the number of ways modulo \(10^9+7\). The answer to 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\)