为了监控加密货币汇率,交易员 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}$$$。