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$ 取模的结果。

样例

样例输入 1

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

样例输出 1

54

说明

该示例共有 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$ 的赛道。

请注意，对于此问题，标准时间限制增加到每个测试用例 3 秒（Java 和 Python 为每个测试用例 6 秒）。

题目来源：Matt Fontaine