Preparing NOJ # Rikka with Quicksort

3000ms 524288K

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

Info Provider HDU

Origin HDU856-1001

Code HDU6680

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 08/19/2019 12:05:19

Related

Nothing Yet