CF868G.El Toll Caves

The prehistoric caves of El Toll are located in Moià (Barcelona). You have heard that there is a treasure hidden in one of n possible spots in the caves. You assume that each of the spots has probability 1 / n to contain a treasure.

You cannot get into the caves yourself, so you have constructed a robot that can search the caves for treasure. Each day you can instruct the robot to visit exactly k distinct spots in the caves. If none of these spots contain treasure, then the robot will obviously return with empty hands. However, the caves are dark, and the robot may miss the treasure even when visiting the right spot. Formally, if one of the visited spots does contain a treasure, the robot will obtain it with probability 1 / 2, otherwise it will return empty. Each time the robot searches the spot with the treasure, his success probability is independent of all previous tries (that is, the probability to miss the treasure after searching the right spot x times is 1 / 2_x_).

What is the expected number of days it will take to obtain the treasure if you choose optimal scheduling for the robot? Output the answer as a rational number modulo 109 + 7. Formally, let the answer be an irreducible fraction P / Q, then you have to output . It is guaranteed that Q is not divisible by 109 + 7.

埃尔托尔史前洞穴位于莫亚（巴塞罗那）。你听说洞穴中某处隐藏着一件宝藏，而该宝藏可能位于 $ n $ 个候选位置中的任意一个。你假设每个位置藏有宝藏的概率均为 $ 1/n $。

你本人无法进入洞穴，因此你制造了一个机器人来代为搜寻宝藏。每天你可以指令机器人恰好访问洞穴中的 $ k $ 个互不相同的位置。若这 $ k $ 个位置中均无宝藏，则机器人显然空手而归。然而，由于洞穴内一片漆黑，即使机器人访问了藏有宝藏的正确位置，它仍有可能错过宝藏。形式化地说：若被访问的位置中恰有一个藏有宝藏，则机器人成功获取该宝藏的概率为 $ 1/2 $，否则将空手返回。每次机器人搜索到宝藏所在位置时，其成功概率均相互独立（即：若宝藏位于某位置，且机器人已对该位置搜索了 $ x $ 次，则仍未找到宝藏的概率为 $ 1/2^x $）。

若你为机器人制定最优的每日搜索计划（即最优调度策略），则获得宝藏所需的期望天数是多少？请以模 $ 10^9 + 7 $ 的有理数形式输出答案。形式化地，设答案为既约分数 $ P/Q $，则你需要输出 。题目保证 $ Q $ 不被 $ 10^9 + 7 $ 整除。

The first line contains the number of test cases T (1 ≤ T ≤ 1000).

Each of the next T lines contains two integers n and k (1 ≤ k ≤ n ≤ 5·108).

第一行包含测试用例的数量 $T$（$1 \leq T \leq 1000$）。

接下来的 $T$ 行，每行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 5\cdot10^8$）。

For each test case output the answer in a separate line.

对于每个测试用例，在单独的一行中输出答案。

In the first case the robot will repeatedly search in the only spot. The expected number of days in this case is 2. Note that in spite of the fact that we know the treasure spot from the start, the robot still has to search there until he succesfully recovers the treasure.

In the second case the answer can be shown to be equal to 7 / 2 if we search the two spots alternatively. In the third case the answer is 25 / 9.

在第一种情况下，机器人将反复在唯一的位置进行搜索。此时的期望天数为 $2$。注意，尽管我们从一开始就知道宝藏所在的位置，机器人仍需持续在此处搜索，直到成功找到宝藏。

在第二种情况下，若交替搜索两个位置，则答案可证明为 $\frac{7}{2}$。在第三种情况下，答案为 $\frac{25}{9}$。