SOLVE

LATER

Counting Number of Ways

/

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

Explanation

For Test case *1* :

\(K= 2\) and \(X = 3\) , so she can reach in *3* ways

*a* \(1,1,1\) (taking all step of one)

*b* \(1,2\) (\(1^{st}\) step one and \(2^{nd}\) as two)

*c* \(2, 1\) (\(1^{st}\) two and \(2^{nd}\) as one)

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...