Journey

One day, Homer was bored at home and decided to set out on a journey to discover the lands of Springfield. The lands of Springfield form an infinite grid. Homer's house is at cell $(0, 0)$, and his journey consists of $N$ steps, where each step is either a move one cell right or a move one cell down.

Already bored, Homer did not want his journey to be boring too. He decided he would not move in the same direction for more than $K$ consecutive steps. So a journey is interesting if, for every $K + 1$ consecutive steps, Homer has moved in both directions.

Figure 1: Example with $N = 5$ and $K = 2$ (first test case)

Given $N$ and $K$, count the interesting journeys Homer can make. Two journeys are different if, for some $i$, the $i$-th step of the first journey differs from the $i$-th step of the second. The count can be large, so print it modulo $1\,000\,000\,007$.

Your program is tested on one or more test cases. The first line of input holds a single integer $T$, the number of test cases ($1 \le T \le 500$), followed by $T$ test cases.

Each test case is given on a single line holding two integers separated by a single space. The first integer is the number of steps in Homer's journey, $N$, and the second integer $K$ is the maximum number of consecutive steps Homer can take while moving in the same direction, where $0 \le N \le 10^5$ and $0 \le K \le 10^5$.

For each test case, print on a single line the number of different journeys Homer can make, modulo $1\,000\,000\,007$.