题目描述

Bessie 和 Farmer John 喜欢山羊卡丁车比赛。这个比赛非常类似于其他人喜欢的卡丁车比赛，除了卡丁车是由山羊拉动，以及赛道是由农田组成。农田由 $N$ 个草地和 $M$ 条道路组成，每条道路都连接着两个草地。

定义农场是两个或更多草地的一个集合，同一农场中的每个草地都可以沿着一系列唯一的道路到达农场中其他任意一个草地。

整个农田可能由多个农场组成，假设图中有 $K$ 个农场。Bessie 希望通过添加长度为 $X$ 的 $K$ 条道路，连接所有 $K$ 个农场来制作山羊卡丁车赛道。每个农场只应访问一次，并且每个农场内必须至少穿过一条道路。

为了让选手们对赛道更有兴趣，赛道的长度至少应该为 $Y$ 。Bessie 希望知道所有这些有趣赛道的赛道长度总和。如果一个赛道中有两个农场直接相连，但另外一个赛道中这两个农场没有直接相连的话，这两个赛道就是不同的。

形式化题意：

给定 $K$ 个连通块的森林，边有边权。你需要加入 $K$ 条长为 $X$ 的边使得整张图变成一棵基环树。原来的每个连通块在环上至少有一条边，所有新加入的边都应该在环上。

求所有环长 $\ge Y$ 的合法方案的环长之和。

输入格式

第一行包括四个整数 $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$（$1 \leq A_i, B_i \leq N,0 \leq D_i \leq 2500$），代表 $A_i$ 号草地和 $B_i$ 号草地间有一条长度为 $D_i$ 的道路。保证两个草地间最多只有一条道路直接相连，且不存在自环。

输出格式

输出有趣赛道的赛道长度总和 $\pmod {10^9+7}$ 后的结果。

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

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)

其中后 4 条赛道满足了赛道总长不低于 12 的条件，这几条赛道的长度总和为 54。

子任务：对于 $70\%$ 的数据， $N,Y \leq 1000$ 。