Guia Pesao P62371

Per moure’s per París, un membre dels equips UPC (aka Pesao) es va oferir per guiar el grup des d’un punt d’origen $s$ fins a un punt de destí $t$. Malgrat les ganes que hi posava, els camins que acabava escollint no eren mai els millors: el grup sempre s’acostava a $t$, però en cap moment s’agafava un carrer que hi anés òptimament.

Específicament, sigui $d(p)$ la distància mínima des de cada punt $p$ fins a $t$. Si en algun moment s’estava en el punt $x$, i hi havia un carrer de longitud $\ell$ que connectava $x$ amb un altre punt $y$, es podia passar pel carrer només si es donaven les dues condicions següents:

• $d(y) < d(x)$, i.e., la distància a $t$ sempre disminuia estrictament.

• No hi havia cap camí de distància mínima per anar des d’$x$ fins a $t$ que passés pel carrer. En altres paraules, $\ell + d(y) > d(x)$.

De quantes maneres es podria haver fet una ruta que anés des d’$s$ fins a $t$ tot complint les condicions anteriors?

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb el nombre de punts $n$, el nombre de carrers bidireccionals $m$, l’origen $s$ i el destí $t$, amb $s \ne t$. Segueixen $m$ ternes amb la informació de cada carrer $x$ $y$ $\ell$, amb $x \ne y$ i $1 \le \ell \le 10^4$. Podeu suposar $2 \le n \le 5 \cdot 10^4$ i $0 \le m \le 5n$. Els punts es numeren entre 0 i $n-1$. Pot haver-hi més d’un carrer entre dos punts donats. També pot ser que no hi hagi cap camí entre $s$ i $t$.

Sortida

Per a cada cas, escriviu el nombre de camins possibles mòdul $10^8 + 7$.