Rikka with Quicksort

Problem Description

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.

Input

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

Output

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

Sample Input

5

3 1

5 1

5 3

10 5

1000 500

Sample Output

666666674

800000013

400000008

308730177

3107840

Source

2019 Multi-University Training Contest 9