Number of ways

★★★★★

5 votes

Open, Open, Open, Dynamic Programming, Algorithms, Easy, Introduction to Dynamic Programming 1

Details

Problem

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

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$

Time Limit: 1

Memory Limit: 256

Source Limit:

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)