Superstition

Today is the long-awaited day for all school students: the first holiday of the new school year. Our heroine Deni is now in grade 10. She prepared for today. She found that there are N stores downtown, and she plans to visit some of them with her friends.

Deni and her friends do not like some of the connections between the stores, so they will not use them. They made a list of M pairs of stores. A pair (x, y) is on the list when they like the connection between stores x and y. That connection works in both directions, and each pair has a travel time that is the same in both directions. No pair connects a store to itself, and no pair appears twice.

The first line of standard input contains four integers N, M, D and K. Each of the next M lines contains three integers $x_i$, $y_i$ and $t_i$, describing a bidirectional connection between stores $x_i$ and $y_i$ with travel time $t_i$ ($1 \le i \le M$).

Print the number of valid routes. Because this number can be large, print its remainder when divided by 1,000,000,007.

A route is valid if it uses connections from the list, its total travel time is divisible by D, and its total travel time is at most K. A store may be visited more than once. Two routes are different if their sequences of visited stores differ.

• $2 \le N \le 80$
• $2 \le M \le 3160$
• $2 \le D \le K \le 10^9$
• $1 \le t_i \le 10$