Counting Number of Ways
/

## Dynamic Programming

Problem
Editorial
Analytics

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$

SAMPLE INPUT
2
3 2
2 2
SAMPLE OUTPUT
3
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

## This Problem was Asked in

Initializing Code Editor...