← 返回题目列表

Codeforces · 868/G

G. 埃尔收费洞穴

中文机器翻译题面 查看原题

El Toll 的史前洞穴位于莫亚(巴塞罗那)。您听说过洞穴中 n 个可能的地点之一隐藏着宝藏。您假设每个地点包含宝藏的概率为 1 / n。

你自己无法进入洞穴,因此你建造了一个可以在洞穴中搜索宝藏的机器人。每天,您可以指示机器人精确访问洞穴中的 k 个不同地点。如果这些地点都没有宝藏,那么机器人显然会空手而归。然而,洞穴里很暗,即使机器人走对了地方,也可能会错过宝藏。正式来说,如果访问过的某个地点确实包含宝藏,机器人将以 1 / 2 的概率获得它,否则它将空返回。机器人每次搜索有宝藏的地点时,其成功概率与之前的所有尝试无关(即,在搜索正确地点 x 次后错过宝藏的概率是 1 / 2x)。

如果机器人选择最优调度,预计需要多少天才能获得宝藏?将答案输出为有理数模 109 + 7。形式上,令答案为不可约分数 P / Q,则必须输出 $$P \cdot Q^{-1} \bmod (10^9 + 7)$$。保证 Q 不能被 109 + 7 整除。

输入

第一行包含测试用例的数量 T (1 ≤ T ≤ 1000)。

接下来的 T 行中的每一行都包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 5·108)。

输出

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

示例

输入 #1

3
1 1
2 1
3 2

输出 #1

2
500000007
777777786

注意

在第一种情况下,机器人将在唯一的位置重复搜索。在这种情况下,预计天数为 2。请注意,尽管我们从一开始就知道宝藏地点,但机器人仍然必须在那里搜索,直到成功找到宝藏。

在第二种情况下,如果我们交替搜索这两个点,则答案可以显示等于 7 / 2。在第三种情况下,答案是 25 / 9。