Travel Tax

Byteland consists of $n$ cities connected by $n - 1$ bidirectional roads. A path along the roads exists between any two cities. The president of Byteland is short exactly $m$ Bytelandian currency units to fulfill all his campaign promises. To raise the needed sum, he decided to introduce a toll on travel along the roads.

After a special commission's work, for each road the minimum and maximum amounts of money that the residents of Byteland are willing to pay to use that road were determined. A survey also revealed that this year exactly one person from each city of Byteland plans to travel to each other city of Byteland.

Every resident traveling from one city to another always chooses the shortest route and follows it. When passing along a road, the resident pays the tax set by the president.

The president of Byteland wonders how many different ways there are to set the tolls on the roads so that the total income is exactly $m$. Two ways are considered different if there is a road whose toll differs between the two ways. Output the answer modulo $10^9 + 7$.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^5$), the number of cities in Byteland and the required sum of money. The next $n - 1$ lines each contain four numbers $a_i$, $b_i$, $l_i$, $r_i$ ($1 \le a_i, b_i \le n$, $1 \le l_i \le r_i \le 5 \cdot 10^5$), meaning that there is a road between cities $a_i$ and $b_i$ on which a toll from $l_i$ to $r_i$ currency units inclusive can be imposed.

Output a single number: the answer to the problem modulo $10^9 + 7$.