J. Сколько дешёвых маршрутов

Как задача H, но посчитайте, сколько маршрутов наименьшей стоимости укладываются в $k$ перелётов. Ответ по модулю $10^9 + 7$.

Маршруты с разным числом перелётов считаются разными, даже если проходят по одним и тем же городам.

Первая строка содержит числа $n$ ($2 \le n \le 100$), $m$ ($1 \le m \le 10^5$), $k$ ($1 \le k \le 100$), $s$ и $f$.

Далее идут $m$ строк: город вылета, город прилёта и стоимость $p$ ($1 \le p \le 10^6$). Возможны кратные рейсы.

Одно число — количество маршрутов наименьшей стоимости по модулю $10^9 + 7$, или $0$, если добраться нельзя.