Кузнечик подальше

Тот же кузнечик, но за один раз он прыгает на любое число ступеней от 1 до $k$. Сколькими способами он доберётся до ступени $n$? Ответ по модулю $10^9 + 7$.

Одна строка: числа $n$ от $0$ до $10^6$ и $k$ от $1$ до $100$.

Одно число.

Прямой перебор всех $k$ переходов даёт $n \cdot k$ действий — сто миллионов. Заметьте, что сумма последних $k$ значений меняется на каждом шаге ровно на два слагаемых: одно приходит, одно уходит. Это скользящее окно из занятия про два указателя.