통행세

바이트랜디아는 $n$개의 도시로 이루어져 있고, 이 도시들은 $n - 1$개의 양방향 도로로 연결되어 있다. 어떤 두 도시 사이에도 도로를 따라 가는 경로가 존재한다. 바이트랜디아의 대통령은 선거 공약을 모두 이행하는 데 필요한 돈이 정확히 $m$바이트랜디아 화폐 단위만큼 부족하다. 필요한 금액을 모으기 위해 대통령은 도로 통행세를 도입하기로 했다.

특별 위원회의 조사 후, 각 도로마다 바이트랜디아 주민들이 그 도로를 이용하기 위해 지불할 의사가 있는 최소 금액과 최대 금액이 정해졌다. 설문 조사 결과, 올해 바이트랜디아의 각 도시에서 다른 모든 도시로 정확히 한 명씩 여행할 예정이라는 것도 밝혀졌다.

한 도시에서 다른 도시로 가는 주민은 항상 최단 경로를 선택해 그 경로로 이동한다. 도로를 지날 때 주민은 대통령이 정한 세금을 낸다.

바이트랜디아 대통령은 도로 통행세를 정해 총 수입이 정확히 $m$이 되게 하는 방법이 몇 가지인지 궁금해한다. 어떤 도로에서 두 방법의 통행세가 다르면 두 방법은 다른 것으로 본다. 답을 $10^9 + 7$로 나눈 나머지를 출력하라.

첫째 줄에는 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 5 \cdot 10^5$). $n$은 바이트랜디아의 도시 수, $m$은 필요한 금액이다. 다음 $n - 1$개 줄에는 각각 네 수 $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$). 이는 도시 $a_i$와 $b_i$ 사이에 도로가 있고, 그 도로에 $l_i$ 이상 $r_i$ 이하의 금액으로 통행세를 부과할 수 있다는 뜻이다.

문제의 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.