| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 13 | 1 | 1 | 100.000% |
Байтландия состоит из n городов, которые соединены n − 1 двусторонними дорогами. Известно, что между любыми двумя городами существует путь по дорогам. Президенту байтландии не хватает ровно m байтландских денежных единиц для выполнения всех своих предвыборных обещаний. Чтобы собрать нужную сумму, он решил ввести налог на проезд по дорогам.
После работы специальной комиссии, для каждой дороги было определено минимальное и максимальное количество денег, которые готовы платить жители Байтландии, чтобы воспользоваться этой дорогой. После опроса также было выяснено, что из каждого города Байтландии в каждый другой город Байтландии в этом году собирается поехать ровно один человек.
Каждый житель, который едет из одного города в другой, всегда выбирает самый кратчайший маршрут и двигается по нему. При проезде по дороге житель платит налог, который был определен президентом.
Президента Байтландии очень волнует вопрос, сколько различных способов назначить налоги на проезд по дорогам, чтобы сумма доходов была ровно m. Два способа считаются различными, если существует дорога, для которой различается налог на проезд в этих способах. Выведите ответ по модулю 109 + 7.
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 5·105) – количество городов Байтландии и необходимая сумма денег. В следующих n − 1 строках записано по четыре числа ai, bi, li и ri (1 ≤ ai, bi ≤ n, 1 ≤ li ≤ ri ≤ 5·105), обозначающие, что между городами ai и bi существует дорога на которую можно ввести налог в размере от li до ri денежных единиц включительно.
Выведите единственное число — ответ на задачу по модулю 109 + 7.
6 152 1 2 3 4 2 3 1 2 2 4 3 5 4 5 1 1 4 6 2 2
2