Rikka with Quicksort

Rikka is interested in computer science, and she has been practicing coding for two years and a half. Today, she wants to do a simple summary of the algorithms she has learned.

One of the most important algorithms is Quicksort. Though its idea is quite simple, Rikka remembers that it took her a while to prove the time complexity. Let $f(n)$ be the expected number of comparisons required by Quicksort on a sequence with length $n$. Then $f(n)$ follows the following equations:
$$
\begin{aligned}
f(0) &= 0 \\
f(i) &= i-1 + \frac{1}{i}\sum_{j=1}^{i}\left( f(j-1) + f(i-j)\right) & i \geq 1
\end{aligned}
$$
After some simple derivations, Rikka finishes the proof and obtains the result that $f(n) = O(n \log n)$: As an outstanding undergraduate student, this problem is just a piece of cake for her.

To make the task more challenging, Rikka asks Yuta, her boyfriend, to set several exercises for her. The following is the hardest one of them:

Consider a modified version of Quicksort: the recursive process terminates once the length of the interval is less than $m$. At this time, the expected number of comparisons $g_m(n)$ can be described with the following equations:
$$
\begin{aligned}
g_m(i) &= 0 & 0 \leq i \leq m\\
g_m(i) &= i-1 + \frac{1}{i}\sum_{j=1}^{i}\left( g_m(j-1) + g_m(i-j)\right) & i > m
\end{aligned}
$$
Now, Yuta shows the value of $n,m$, and he wants Rikka to calculate $g_m(n)$. It is generally known that Rikka is not good at math. Therefore she wants you to help her calculate the answer.

The first line is an integer $t(1 \leq t \leq 10)$, the number of test cases.

For each test case, the input contains a single line with two positive integers $n,m(1 \leq m \leq n \leq 10^9)$.

For each test case, output a single line with a single number, the value of $g_m(n)$.

Clearly, $g_m(n)$ is a rational number. Therefore, you are required to print $g_m(n)\ \text{mod}\ 1000000007$, i.e., print $x \times y^{-1}\ \text{mod}\ 1000000007$ where $\frac{x}{y}$ is the irreducible fraction representation of $g_m(n)$.

5
3 1
5 1
5 3
10 5
1000 500

666666674
800000013
400000008
308730177
3107840

2019 Multi-University Training Contest 9