← 返回题目列表

Codeforces · 1523/E

E. 加密灯

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

为了监控加密货币汇率,交易员 William 发明了一种奇妙的设备,由排成一排的 $$$n$$$ 灯组成。该设备按以下方式工作:

最初,William 设备上的所有灯都关闭。在新的迭代开始时,设备以均匀分布随机选择一盏关闭的灯并将其打开,告诉 William 他应该投资哪种加密货币。在本次迭代之后,如果任何 $$$k$$$ 连续灯包含多个打开的灯,则设备完成工作。

William 不喜欢不确定性,因此他希望您计算设备完成工作后打开的灯数量的预期值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 10^5$$$),分别是正在检查的灯光总数和灯光子段的长度。

输出

对于每个测试用例,打印答案,模 $$$10^9+7$$$。

正式地,令 $$$M = 10^9+7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

3
3 2
15 2
40 15

输出 #1

333333338
141946947
329622137

注意

第一个示例测试用例的说明:

让我们写出所有可能的灯光切换序列,这将使设备完成其操作:

1. $$$(1, 2)$$$  — $$$2$$$ 灯亮起
2. $$$(1, 3, 2)$$$  — $$$3$$$ 灯亮起
3. $$$(2, 1)$$$  — $$$2$$$ 灯亮起
4. $$$(2, 3)$$$  — $$$2$$$ 灯亮起
5. $$$(3, 2)$$$  — $$$2$$$ 灯亮起
6. $$$(3, 1, 2)$$$  — $$$3$$$ 灯亮起

那么最终的期望值将等于 $$$\frac{2}{6}$$$ + $$$\frac{3}{6}$$$ + $$$\frac{2}{6}$$$ + $$$\frac{2}{6}$$$ + $$$\frac{2}{6}$$$ + $$$\frac{3}{6}$$$ = $$$\frac{14}{6}$$$ = $$$\frac{7}{3}$$$。

那么所需的输出将是 $$$333333338$$$,因为 $$$333333338 \cdot 3 \equiv 7 \pmod{10^9+7}$$$。