## 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