CF1523E Crypto Lights

 为了监控加密货币的汇率，交易员 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}$。输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

第一个样例的解释： 我们列出所有可能使装置停止工作的点亮顺序： 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}$。 由 ChatGPT 4.1 翻译