Для отслеживания курса криптовалют трейдер Василий изобрел удивительный прибор, состоящий из $$$n$$$ лампочек, расположенных в ряд. Прибор работает следующим образом:
Изначально все лампочки в приборе Василия выключены. На очередной итерации прибор Василия равновероятно выбирает выключенную лампочку и включает её, подсказывая Василию, в какую криптовалюту ему стоит вложиться. Если после этой итерации среди каких-то $$$k$$$ подряд идущих лампочек находится более одной включенной, то прибор Василия завершает свою работу.
Василий не любит неопределенности, поэтому просит вас посчитать матожидание количества включенных лампочек в приборе после завершения его работы.
Во входных данных находится несколько наборов входных данных. В первой строке находится одно целое число $$$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}$$$.
3 3 2 15 2 40 15
333333338 141946947 329622137
Объяснение первого тестового примера:
Выпишем все возможные последовательности включений лампочек, которые завершают работу прибора:
- $$$(1, 2)$$$ — включены $$$2$$$ лампочки
- $$$(1, 3, 2)$$$ — включены $$$3$$$ лампочки
- $$$(2, 1)$$$ — включены $$$2$$$ лампочки
- $$$(2, 3)$$$ — включены $$$2$$$ лампочки
- $$$(3, 2)$$$ — включены $$$2$$$ лампочки
- $$$(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}$$$.
