You are given a weighted tree T and an integer MAXW . You have to count the number of weighted graphs whose non-negative edges weigh at most MAXW and T is an MST(minimum spanning tree) for that graph. Print the result modulo 987654319.

Input

First line: Two integers n and MAXW denoting the number of vertices of the given tree and the maximum allowed weight of an edge respectively (1<=n<=300000)

Next N-1 lines: Describes the tree, each of which contains three integers,v,u,w , which means that there is an edge connecting the vertices v and u with a weight equal to w (0<=MAXW,w <=10^9)

It is guaranteed that the given graph forms a tree.

Output

Print only one integer, the number of desired graphs modulo 987654319.

Input

First line: Two integers n and MAXW denoting the number of vertices of the given tree and the maximum allowed weight of an edge respectively (1<=n<=300000)

Next N-1 lines: Describes the tree, each of which contains three integers,v,u,w , which means that there is an edge connecting the vertices v and u with a weight equal to w (0<=MAXW,w <=10^9)

It is guaranteed that the given graph forms a tree.

Output

Print only one integer, the number of desired graphs modulo 987654319.

Please describe what you've done, or how you think you can solve the problem. We won't just solve it for you.

I have tried making mst from given tree. While creating mst as I was adding edges I checked it wether it would form a cycle or not. If it will form a cycle then I would find the maximum edge till now i.e current edge. And then multiplying them under modulo m

> I have tried making mst from given tree

the mst of a tree is the tree itself...

> I checked it wether it would form a cycle or not

you have a tree, a tree does not have cycles...

> I would find the maximum edge till now i.e current edge.

an easy search then...

> And then multiplying them under modulo m

wonder how do you multiply edges...

you are not explaining yourself.

the mst of a tree is the tree itself...

> I checked it wether it would form a cycle or not

you have a tree, a tree does not have cycles...

> I would find the maximum edge till now i.e current edge.

an easy search then...

> And then multiplying them under modulo m

wonder how do you multiply edges...

you are not explaining yourself.

Topic archived. No new replies allowed.