Counting Valid Node Weight Assignments in a Tree

You are given a tree with n nodes numbered from 1 to n. Initially every node has a hidden integer weight in the range \( [l, r] \) (inclusive). Some of the \( n-1 \) edges additionally have an integer weight associated with them, while others do not. For every edge with an associated weight \( x \), the weights \( a_u \) and \( a_v \) of the nodes it connects must satisfy the equation:

[ a_u + a_v = x ]

For edges without an associated weight, there is no restriction. Two assignments are considered different if there exists at least one node whose weight differs. Your task is to count the number of different valid assignments of node weights that satisfy all the constraints.

Note: Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The first line contains three integers \( n, l, r \) – the number of nodes in the tree and the inclusive range of possible weights for each node.

Each of the next \( n-1 \) lines contains three integers \( u, v, x \) describing an edge between nodes \( u \) and \( v \). If \( x = -1 \), then the edge has no weight constraint; otherwise, the edge has weight \( x \) and it imposes the condition \( a_u + a_v = x \).

It is guaranteed that the given graph is a tree.

outputFormat

Output a single integer – the number of valid node weight assignments modulo \(10^9+7\).

sample

3 1 3
1 2 -1
2 3 -1

27