미신

오늘은 모든 학생이 오랫동안 기다려 온 날, 새 학년의 첫 휴일이다. 주인공 데니는 이제 10학년이다. 데니는 오늘을 위해 준비했고, 시내에 가게가 $N$개 있다는 것을 알아냈다. 데니는 친구들과 그중 몇 곳을 방문할 계획이다.

데니와 친구들은 가게 사이의 일부 연결을 좋아하지 않아서 그 연결은 이용하지 않기로 했다. 그래서 가게 쌍의 목록을 $M$개 만들었다. 가게 $x$와 $y$ 사이의 연결을 좋아하면 쌍 $(x, y)$를 목록에 넣는다. 이 연결은 양방향으로 통하며, 이동 시간은 어느 방향이든 같다. 같은 가게끼리 잇는 쌍은 없고, 같은 쌍이 두 번 나오지도 않는다.

첫 번째 줄에 정수 $N$, $M$, $D$, $K$가 주어진다. 이어지는 $M$개의 줄에는 각각 정수 $x_i$, $y_i$, $t_i$가 주어지며, 이는 가게 $x_i$와 $y_i$를 양방향으로 잇고 이동 시간이 $t_i$인 연결을 뜻한다 ($1 \le i \le M$).

유효한 경로의 수를 출력한다. 이 수가 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

경로는 목록에 있는 연결만 사용하고, 총 이동 시간이 $D$로 나누어떨어지며 $K$ 이하일 때 유효하다. 같은 가게를 여러 번 방문해도 된다. 방문한 가게의 순서가 다르면 서로 다른 경로이다.

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