All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?