题目描述

今天是所有学生都期待已久的日子——新学年的第一个假期。我们的主角 Deni 现在上 10 年级。她为今天做好了准备：她发现市中心有 $N$ 家商店，打算和朋友们去逛其中的一些。

不过，Deni 和她的朋友们并不喜欢某些商店之间的连接，所以她们不会使用这些连接。于是，她们列出了 $M$ 对商店，若 $(x, y)$ 在这个列表中，就表示她们喜欢从商店 $x$ 到商店 $y$ 的这条连接，并且当然也可以从 $y$ 到 $x$ 到达；对于每一对商店，她们还记录了在这条连接上行走所需的时间（两个方向相同）。保证不会出现编号相同的商店对，也不会有重复的商店对。

Deni 非常迷信，她相信的一条迷信规则是：总旅行时间必须能被 $D$ 整除。

另外，Deni 和朋友们的时间并不是无限的，因此她们最多只能花费 $K$ 的时间在路上。

和所有女孩子一样，Deni 很好奇，于是她开始数：到底有多少条不同的路线可以用来逛若干家商店（一个商店可以被访问多次）。不幸的是，这个数量可能非常大。于是 Deni 想到了你——一位非常优秀的程序员——请你编写程序 superstition 来计算合法路线的数量。

若一条路线满足以下条件，则称其为合法路线：

• 只使用给定列表中的连接；
• 总旅行时间能被 $D$ 整除；
• 总旅行时间不超过 $K$。

若两条路线访问商店的序列不同，则认为它们是不同的路线。

你很快注意到答案可能很大，因此 Deni 只需要你输出答案对 $1{,}000{,}000{,}007$ 取模后的结果。

输入格式

第一行输入四个整数 $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$ 取模后的结果。

数据范围

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

子任务与评分

子任务	分值	$N$	$M$	$D$	$K$	额外限制
1	5	$N \le 5$	$M \le 10$	$D \le 12$	$K \le 12$	无
2	30	$N \le 80$	$M \le 3160$	$D \le 10^4$	$K \le 10^4$
3	10	$N \le 20$	$M \le 190$	$D \le 10^9$	$K \le 10^9$	$D = K$ 且 $\sum_{i=1}^{M} t_i \le 200$
4	20					$\sum_{i=1}^{M} t_i \le 200$
5	15	$N \le 30$	$M \le 435$			$D = K$
6	20					无

只有当某个子任务中的所有测试点都通过时，你才能得到该子任务的分数。

样例 1

输入

3 3 2 2
1 2 1
2 3 2
3 1 1

输出

8

样例解释

这里 $D = K = 2$，因此所需的路线只可能是总时间恰好为 $2$ 的路线。它们是：

1-2-1
2-1-2
3-1-3
1-3-1
2-3
3-2
2-1-3
3-1-2

注意，商店和连接都可以被重复经过多次。

样例 2

输入

5 7 5 10
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4

输出

58

样例解释

因为 $D < K$，所以需要统计总时间为 $5$ 和 $10$ 的路线。

样例 3

输入

5 9 2 20
1 2 1
2 3 2
3 1 1
3 4 1
4 5 2
5 3 1
1 5 1
2 4 1
2 5 1

输出

989802661

样例解释

这里真实答案非常大，因此输出的只是它对 $1{,}000{,}000{,}007$ 取模后的结果。

样例 4

输入

5 7 5000000 5000000
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4

输出

598634781

样例解释

这里真实答案也非常大，因此输出的只是它对 $1{,}000{,}000{,}007$ 取模后的结果。