CF1523E.Crypto Lights

To monitor cryptocurrency exchange rates trader William invented a wonderful device consisting of $n$ lights arranged in a row. The device functions in the following way:

Initially, all lights on William's device are turned off. At the beginning of a new iteration the device randomly, with a uniform distribution, picks a light that is turned off and turns it on, telling William which cryptocurrency he should invest in. After this iteration if any $k$ consecutive lights contain more than one turned on light, then the device finishes working.

William doesn't like uncertainty, so he wants you to calculate the expected value of the number of lights that are turned on in the device after it finishes working.

为了监控加密货币汇率，交易员威廉发明了一种精妙的装置，该装置由排成一行的 $n$ 个灯组成。该装置的工作方式如下：

初始时，威廉装置上的所有灯均处于关闭状态。在每一次迭代开始时，装置会均匀随机地从所有关闭的灯中选择一个并将其打开，以此向威廉指示他应投资哪一种加密货币。在此迭代之后，若存在任意 $k$ 个连续的灯，其中开启的灯的数量超过一个，则该装置即停止工作。

威廉不喜欢不确定性，因此他希望你计算：当装置停止工作时，已开启的灯的数量的期望值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). Description of the test cases follows.

The only line for each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 10^5$), which are the total number of lights and the length of subsegment of lights that are being checked, respectively.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $k$（$2 \le k \le n \le 10^5$），分别表示灯的总数以及正在检查的灯的子段长度。

For each test case print the answer, modulo $10^9+7$.

Formally, let $M = 10^9+7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对每个测试用例，输出答案对 $10^9+7$ 取模的结果。

形式化地，令 $M = 10^9+7$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

Explanation of the first sample test case:

Let's write out all possible sequences of light toggles, which will make the device complete its operation:

1. $(1, 2)$ — $2$ lights are turned on
2. $(1, 3, 2)$ — $3$ lights are turned on
3. $(2, 1)$ — $2$ lights are turned on
4. $(2, 3)$ — $2$ lights are turned on
5. $(3, 2)$ — $2$ lights are turned on
6. $(3, 1, 2)$ — $3$ lights are turned on

Then the final expected value will be equal to $\frac{2}{6}$ + $\frac{3}{6}$ + $\frac{2}{6}$ + $\frac{2}{6}$ + $\frac{2}{6}$ + $\frac{3}{6}$ = $\frac{14}{6}$ = $\frac{7}{3}$.

Then the required output will be $333333338$, since $333333338 \cdot 3 \equiv 7 \pmod{10^9+7}$.

第一个样例测试用例的解释：

我们列出所有可能的开关灯序列，这些序列将使设备完成其运行：

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}$。