무리오 카트

Bessie와 Farmer John은 염소 카트 경주를 즐긴다. 다른 이들이 즐기는 카트 경주와 아주 비슷하지만, 카트를 염소가 끌고 트랙은 근처 농지로 만든다는 점이 다르다. 농지는 $N$개의 초원과 $M$개의 도로로 이루어지며, 각 도로는 두 초원을 연결한다.

Bessie는 근처 농장들로 코스를 만들려고 한다. 농장이란 두 개 이상의 초원으로 이루어진 집합으로, 그 안의 모든 초원이 유일한 도로 순서를 따라 서로에게 도달할 수 있는 것이다.

근처 농지에는 여러 농장이 있을 수 있다. 농장이 $K$개라고 하자. Bessie는 $K$개의 농장을 길이 $X$인 도로 $K$개로 연결해 염소 카트 루프를 만들려고 한다. 각 농장은 정확히 한 번 방문해야 하고, 각 농장 안에서는 적어도 하나의 도로를 지나야 한다.

경주자에게 흥미로운 코스를 만들기 위해 트랙의 총 길이는 적어도 $Y$여야 한다. Bessie는 그러한 흥미로운 트랙 모두에 대해 트랙 길이의 합을 알고 싶어 한다. 어떤 트랙에서 두 초원이 인접하고(농장 사이에 도로를 추가한 뒤) 다른 트랙에서는 인접하지 않으면 두 트랙은 서로 다르다. 염소 카트가 도로를 따라 이동하는 방향은 고려하지 않고 선택한 도로만 중요하다는 점에 유의하라.

첫째 줄에 $N$, $M$, $X$, $Y$가 주어진다. 여기서 $1 \leq N \leq 1500$, $1 \leq M \leq N-1$, $0 \leq X, Y \leq 2500$이다.

다음 $M$개의 줄이 도로를 나타낸다. 각 줄은 $A_i$ $B_i$ $D_i$ 형태이며, 초원 $A_i$와 $B_i$가 길이 $D_i$인 도로로 연결됨을 뜻한다($1 \leq A_i, B_i \leq N$, $0 \leq D_i \leq 2500$). 모든 초원에는 적어도 하나의 도로가 붙어 있고, 도로의 사이클은 없다.

적어도 70%의 테스트 케이스에서는 $N \leq 1000$이고 $Y \leq 1000$임이 추가로 보장된다.

흥미로운 트랙 모두에 대해 트랙 길이의 합을 나타내는 정수 하나를 출력한다. 합이 매우 클 수 있으므로 길이의 합을 $10^9+7$로 나눈 나머지를 출력한다.

이 예제에는 6개의 가능한 트랙이 있다.

• 1 --> 2 --> 4 --> 5 --> 1 (길이 11)
• 1 --> 2 --> 5 --> 4 --> 1 (길이 11)
• 2 --> 3 --> 4 --> 5 --> 2 (길이 12)
• 2 --> 3 --> 5 --> 4 --> 2 (길이 12)
• 1 --> 2 --> 3 --> 4 --> 5 --> 1 (길이 15)
• 1 --> 2 --> 3 --> 5 --> 4 --> 1 (길이 15)

답은 $12+12+15+15=54$이며, 길이가 적어도 12인 트랙만 더한다.