Bessie y el granjero John disfrutan con las carreras de karts de cabras. La idea es muy similar a las carreras de Go-Kart que otros disfrutan, excepto que los karts son tirados por cabras y la pista está hecha de tierras de cultivo cercanas. Las tierras de cultivo consisten de ~N~ prados y ~M~ caminos, cada uno de los cuales conecta un par de prados.

Bessie quiere hacer un circuito a partir de las granjas cercanas. Una granja es un subconjunto de dos o más prados dentro del cual cada prado puede llegar a todos los demás a lo largo de una secuencia única de caminos.

Las granjas cercanas pueden contener múltiples granjas. Supongamos que hay ~K~ granjas. Bessie quiere hacer un bucle de karts de cabra conectando todas las ~K~ granjas mediante la adición de ~K~ caminos de longitud ~X~. Cada granja debe ser visitada exactamente una vez y al menos un camino debe ser atravesado dentro de cada granja.

Para que el recorrido sea interesante para los corredores, la longitud total de la pista debe ser al menos ~Y~.Bessie quiere saber la suma, sobre todas esas pistas interesantes, de las longitudes totales de las pistas. Una pista es diferente de otra si hay dos prados que son adyacentes (después de añadir los caminos entre las granjas) en una pista pero no en la otra. Por favor, ten en cuenta que sólo importan los caminos elegidos, y no la dirección en la que los karts de cabra se desplazarán por esos caminos.

Entrada

La primera línea de entrada contiene ~N, M, X,~ e ~Y~ donde ~1 \leq N \leq 1500, 1 \leq M \leq N-1,~ y ~0 \leq X,\leq 2500 ~.

Cada una de las ~M~ líneas siguientes describen carreteras. Las líneas son de la forma: ~A_i B_i D_i~, lo que significa que los prados ~A_i~ y ~B_i~ están conectados con un camino de longitud entera ~D_i (1 \leq A_i,B_i \leq N, 0 \leq D_i \leq 2500)~. Cada pradera es incidente con al menos una carretera, y no hay ciclos de carreteras.

En al menos el 70% de los casos de prueba, también se garantiza que ~N \leq 1000~ e ~Y \leq 1000~.

Salida

Salida de un único número entero, que da la suma de las longitudes de las pistas sobre todas las pistas interesantes. Como la suma de las longitudes de las pistas puede ser bastante grande, imprime la suma de las longitudes módulo ~10^9+7~.

Ejemplo de Entrada

5 3 1 12
1 2 3
2 3 4
4 5 6

Ejemplo de Salida

54

Este ejemplo tiene 6 pistas posibles

1 ~\rarr~ 2 ~\rarr~ 4 ~\rarr~ 5 ~\rarr~ 1 (longitud 11)

1 ~\rarr~ 2 ~\rarr~ 5 ~\rarr~ 4 ~\rarr~ 1 (longitud 11)

2 ~\rarr~ 3 ~\rarr~ 4 ~\rarr~ 5 ~\rarr~ 2 (longitud 12)

2 ~\rarr~ 3 ~\rarr~ 5 ~\rarr~ 4 ~\rarr~ 2 (longitud 12)

1 ~\rarr~ 2 ~\rarr~ 3 ~\rarr~ 4 ~\rarr~ 5 ~\rarr~ 1 (longitud 15)

1 ~\rarr~ 2 ~\rarr~ 3 ~\rarr~ 5 ~\rarr~ 4 ~\rarr~ 1 (longitud 15)

La respuesta es ~12+12+15+15=54~, sumando sólo las pistas en las que la longitud es de al menos ~12~.