| JPC 4.0 |
|---|
| Finished |
Zain has a very cute cat, called Khokha, which he keeps showing Ahmad pictures of; so Ahmad decided he will gift him and his cat this problem.
Khokha Khokha likes jumping around like any other cat, she specifically can jump no longer than $$$k$$$ tiles from where she is at now, meaning if she is at tile $$$i$$$ then she could jump to any tile $$$j$$$ $$$(i \lt j \leq n)$$$ such that $$$j - i \leq k$$$.
There are $$$n$$$ aligned tiles, and Khokha starts at tile $$$0$$$. In how many ways can she reach tile number $$$n$$$?
The first line contains one integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.
The next $$$t$$$ lines each contain two integers $$$n$$$ and $$$k$$$ $$$(1 \leq k \leq n \leq 10^6)$$$.
It's guaranteed that the sum of $$$n$$$ over all test cases is not greater than $$$2\cdot10^6$$$.
For each test case, print one integer, the number of ways Khokha can reach tile $$$n$$$ modulo $$$10^9 + 7$$$.
52 12 23 13 23 3
1 2 1 3 4
| Name |
|---|


