B. 完美的集合

小 A 有一棵 个点的带边权的树，树的每个节点有重量 和价值 。

现在小 A 要从中选出若干个节点形成一个集合 ，满足这些节点重量之和 并且构成一个连通块。小 A 是一个完美主义者，因此他只会选择节点价值之和最大的那些 。我们称这样的集合 为完美的集合。

现在小 要从所有完美的集合中选出 个，并对这 个完美的集合分别进行测试。在这 次测试开始前，小 A 首先需要一个点 来放置他的测试装置，这个测试装置的最大功率为 。

接下来的每次测试，小 A 会对测试对象 中的所有点进行一次能量传输，对一个点 进行能量传输需要的功率为 ，其中 表示点 在树上的最短路长度。因此，如果 中存在一个点 ，满足 ，测试就会失败。同时，为了保证能量传输的稳定性，测试装置所在的点 需要在集合 中，否则测试也会失败。

现在小 A 想知道，有多少种从所有完美的集合选出 个的方法，使得他能找到一个放置测试装置的点，来完成他的测试呢？

你只需要输出方案数对 取模的结果。

第一行四个正整数，表示 。

接下来一行 个正整数，表示 。

接下来一行 个非负整数，表示 。

接下来 行，每行三个正整数 ，表示树上存在一条长度为 的边连接节点 。

一个数，表示方案数第 取模的结果。

样例输入

7 3 2 4
1 1 2 2 1 2 2
1 1 1 2 1 2 2
1 2 1
1 3 2
1 4 2
2 5 1
2 6 2
4 7 3

样例输出

2

样例解释

完美的集合有 。

从中选出 个且能完成测试的方案为选择 或选择 。

对于 的数据，。