Zenyk 和 Marichka 家里要举办一场大型派对，他们的 $K$ 位朋友将会到来。

Zenyk 正在尝试寻找一种安置所有朋友的方法。他们的房子由 $N$ 个房间和 $N - 1$ 条走廊组成。每条走廊连接两个房间，并具有一定的长度。通过走廊，可以从任意房间到达其他任何房间。

Zenyk 将满足以下条件的安置方案称为“好的”：

• 每位朋友都住在某个房间里。
• 没有两位朋友住在同一个房间。
• 存在一个房间（无论是否有人居住），使得所有朋友都能在该房间集合，且该房间到每位朋友所在房间的距离都不超过 $L$。

现在，Zenyk 想要计算“好的”安置方案的数量。如果至少有一位朋友住在不同的房间，则认为两个方案是不同的。由于这个数字可能非常大，请输出其对 $1000000007$ 取模的结果。

输入格式

第一行包含 3 个整数 $N, K$ 和 $L$ ($1 \le K \le N \le 10^5, 1 \le L \le 10^9$)。接下来的 $N - 1$ 行，每行包含 3 个整数 $A_i, B_i$ 和 $C_i$ ($1 \le A_i, B_i \le N, 1 \le C_i \le 10^9$)，表示存在一条连接 $A_i$ 和 $B_i$ 的走廊，长度为 $C_i$。

输出格式

输出一个整数，即“好的”安置方案的数量对 $1000000007$ 取模的结果。

样例

输入 1

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

输出 1

12

说明

所有“好的”安置方案为： $\{1, 2\}, \{1, 4\}, \{1, 5\}, \{2, 1\}, \{2, 4\}, \{2, 5\}, \{4, 1\}, \{4, 2\}, \{4, 5\}, \{5, 1\}, \{5, 2\}, \{5, 4\}$。 每一对整数分别代表第一位和第二位朋友所在的房间编号。