Accommodation Plan

Limits: 4 sec., 256 MiB

The big party will be held at Zenyk and Marichka’s home. Their \(K\) friends will arrive to them.

Now Zenyk tries to find a way to accommodate all friends. Their house consists of \(N\) rooms and \(N-1\) hallways. Each hallway connects 2 rooms and has some length. It’s possible to reach any room starting from any room via hallways.

Zenyk calls accommodation plan good if

• Each friend lives in some room.

• No 2 friends live in the same room.

• There exist a room (doesn’t matter if someone lives there) such that all friends can meet in this room and the distance from it to room of each friend is not bigger than \(L\).

Now Zenyk wants to count the number of good accommodation plans. Two plans are considered different if at least one friend lives in different rooms. As this number can be very big, print it modulo 1000000007.

Input

The first line contains 3 integers – \(N\), \(K\) and \(L\). Each of the next \(N-1\) lines contain 3 integers – \(A_i\), \(B_i\) and \(C_i\), which mean that a hallway connecting \(A_i\) and \(B_i\) exists with length \(C_i\).

Output

Print one integer – number of good accommodation plans modulo \(1000000007\).

Constraints

\(1 \le K \le N \le 10^5\),

\(1 \le A_i, B_i \le N\),

\(1 \le C_i, L \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
5 2 7 1 2 4 3 2 8 2 4 2 4 5 6	12

Notes

All good accommodation plans:

\(\{1,2\}, \{1,4\}, \{1,5\}, \{2,1\}, \{2,4\}, \{2,5\}, \{4,1\}, \{4,2\}, \{4,5\}, \{5,1\}, \{5,2\}, \{5,4\}\).

A pair of integers represents room indices of the first and the second friend, respectively.