GPS 해킹

데니스는 학생이고 데이터 보안 시험에서 떨어져서 오늘 재시험을 본다. 그는 늦게 일어나서 택시를 타기로 했다.

데니스는 $n$개의 교차로와 $m$개의 양방향 도로로 이루어진 도시에 산다. 각 도로를 주행하는 데 걸리는 시간이 주어진다. 데니스는 교차로 $s$ 근처에 살고, 대학교는 교차로 $t$ 근처에 있다. 택시가 대학교 근처에 도착하면 데니스는 곧바로 택시에서 내려 시험장으로 달려간다.

문제는 조금 더 복잡하다. 해커가 데니스가 탄 택시의 GPS를 해킹했다. GPS가 정상적으로 작동하면 목적지까지 가장 빠르게 가는 길을 안내한다. 각 교차로에서 가장 빠르게 여정을 끝내는 도로를 보여준다. 가능한 도로가 여러 개라면 GPS는 그중 아무 도로나 보여줄 수 있다. 해커는 GPS가 원하는 도로를 보여주도록 조작할 수 있는데, 그 횟수는 최대 한 번이다.

데니스는 대학교까지 정확히 어떻게 왔는지 기억하지 못하지만, 주행에 걸린 시간 $L$은 기억한다. 선생님은 GPS 공격을 이미 알고 있었기에, 재시험의 일부로 데니스에게 집에서 대학교까지 가능한 경로의 수를 계산하라고 했다.

GPS 해킹을 고려했을 때, 교차로 $s$에서 $t$까지 주행 시간이 정확히 $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$). 두 교차로 $v$와 $u$를 잇는 도로이며, 그 도로를 주행하는 데 $w$의 시간이 걸린다는 뜻이다.

모든 도로는 양방향이며, 두 교차로를 잇는 도로는 최대 하나다. 자기 자신과 잇는 도로는 없다. $s$에서 $t$로 갈 수 있다는 것이 보장된다.

데니스가 $s$에서 $t$까지 이동하며 총 주행 시간이 정확히 $L$이 된 경로로, 가능했던 경로의 수를 $10^9 + 7$로 나눈 나머지로 출력한다.