J. Сколько маршрутов ровно за k

Как классная задача J, но перелётов должно быть ровно $k$.

Считать проще, чем в классной: не нужно сравнивать слои между собой, ответ берётся из последнего слоя целиком.

Ветки «строго лучше» и «столько же» остаются, и порядок их по-прежнему существен.

Ответ выводится по модулю $10^9 + 7$; если маршрутов ровно из $k$ перелётов нет, выведите $0$.

Первая строка содержит числа $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$). Возможны кратные рейсы.

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