I. Zain's Birthday
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$?

Input

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$$$.

Output

For each test case, print one integer, the number of ways Khokha can reach tile $$$n$$$ modulo $$$10^9 + 7$$$.

Example
Input
5
2 1
2 2
3 1
3 2
3 3
Output
1
2
1
3
4