加密货币灯

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

一台装置由排成一行的 $n$ 盏灯组成，初始时所有灯都熄灭。

每轮开始时，装置会在所有尚未点亮的灯中等概率随机选择一盏并将其点亮。随后，如果存在一段长度恰为 $k$ 的连续区间，其中点亮的灯超过一盏，装置就立即停止工作。

求装置停止工作时，点亮灯数的期望值。答案对 $10^9+7$ 取模。

输入格式

第一行包含测试数据组数 $t$。

接下来 $t$ 行，每行包含两个整数 $n,k$，分别表示灯的数量和被检查的连续区间长度。

输出格式

对每组测试数据输出一行答案。

形式化地，设 $M=10^9+7$。若期望值的最简分数为 $p/q$，输出唯一的整数 $x$，满足 $0\le x<M$ 且 $xq\equiv p\pmod M$。

样例输入 1

3
3 2
15 2
40 15

样例输出 1

333333338
141946947
329622137

样例说明

当 $n=3,k=2$ 时，所有可能的停止序列分别为 $(1,2)$、$(1,3,2)$、$(2,1)$、$(2,3)$、$(3,2)$、$(3,1,2)$，停止时点亮灯数的期望为 $14/6=7/3$。

数据范围

对于所有测试数据，$1\le t\le 10$，$2\le k\le n\le 10^5$。