Задача №115270. Взлом навигатора
У студента Дениса сегодня очередная пересдача экзамена по информационной безопасности. Он поздно проснулся и опаздывал, поэтому заказал такси.
Город, в котором живет Денис, можно представить в виде \(n\) перекрёстков, которые соединены \(m\) двусторонними дорогами. Про каждую дорогу известно, за какое время можно по ней проехать. Дом Дениса расположен на перекрёстке с номером \(s\), а университет — возле перекрёстка с номером \(t\). Как только такси доедет до перекрёстка с университетом, Денис немедленно покинет машину и побежит на пересдачу.
Однако не все так просто — как раз сегодня хакеры взломали навигатор в такси. Обычно навигатор помогает следовать по кратчайшему пути до пункта назначения: на каждом перекрестке навигатор показывает, по какой дороге нужно проехать, чтобы добраться до пункта назначения как можно быстрее. Если таких дорог несколько, навигатор может указать любую. Благодаря взлому хакеры могут заставить навигатор не более одного раза во время движения показать в качестве маршрута любую дорогу, на усмотрение хакеров.
Денис не запомнил маршрут, но ему известно время \(L\), которое заняла поездка до университета. Оказалось, что преподаватель знает о хакерской атаке, и в качестве задания для пересдачи он просит Дениса посчитать количество различных способов, которыми он мог добраться до университета за время \(L\).
Помогите Денису посчитать количество путей от его дома до университета, перемещение по которым занимает время \(L\), таких, что такси может поехать по этому пути с учетом взлома навигатора. Поскольку путей может быть очень много, выведите остаток от деления количества путей на \(10^9 + 7\)
В первой строке ввода даны два целых числа \(n\), \(m\) — количество перекрёстков и дорог в городе, где живет Денис (\(2 \leq n \leq 2 \cdot 10^5\), \(1 \leq m \leq \min{(2 \cdot 10^5, \frac{n(n - 1)}{2})}\)).
Во второй строке даны три целых числа \(s\), \(t\) и \(L\) (\(1 \leq s, t \leq n\), \(s \neq t\), \(1 \leq L \leq 2 \cdot 10^{14}\)) — номер перекрёстка с домом Дениса, номер перекрёстка с университетом и время поездки Дениса.
В следующих \(m\) строках содержатся описания дорог между перекрёстками. Описание состоит из трёх целых чисел \(v\), \(u\) и \(w\) (\(1 \leq v, u \leq n\), \(v \neq u\), \(1 \leq w \leq 10^9\)) — номеров двух перекрёстков, которые связывает дорога, и времени, которое требуется для проезда по ней.
Все дороги двусторонние, между любой парой перекрёстков существует не более одной соединяющей их дороги. Никакая дорога не соединяет перекресток сам с собой. Гарантируется, что из перекрёстка \(s\) можно доехать до перекрёстка \(t\).
Выведите единственное целое число — количество маршрутов, по которым мог проехать Денис, взятое по модулю \(10^9 + 7\).
6 7 1 6 12 1 2 2 1 3 4 2 5 2 3 5 4 2 4 4 4 6 6 5 6 4
4