22107번 - Налог на проезд 다국어

Байтландия состоит из n городов, которые соединены n − 1 двусторонними дорогами. Известно, что между любыми двумя городами существует путь по дорогам. Президенту байтландии не хватает ровно m байтландских денежных единиц для выполнения всех своих предвыборных обещаний. Чтобы собрать нужную сумму, он решил ввести налог на проезд по дорогам.

После работы специальной комиссии, для каждой дороги было определено минимальное и максимальное количество денег, которые готовы платить жители Байтландии, чтобы воспользоваться этой дорогой. После опроса также было выяснено, что из каждого города Байтландии в каждый другой город Байтландии в этом году собирается поехать ровно один человек.

Каждый житель, который едет из одного города в другой, всегда выбирает самый кратчайший маршрут и двигается по нему. При проезде по дороге житель платит налог, который был определен президентом.

Президента Байтландии очень волнует вопрос, сколько различных способов назначить налоги на проезд по дорогам, чтобы сумма доходов была ровно m. Два способа считаются различными, если существует дорога, для которой различается налог на проезд в этих способах. Выведите ответ по модулю 10⁹ + 7.

Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 5·10⁵) – количество городов Байтландии и необходимая сумма денег. В следующих n − 1 строках записано по четыре числа a_i, b_i, l_i и r_i (1 ≤ a_i, b_i ≤ n, 1 ≤ l_i ≤ r_i ≤ 5·10⁵), обозначающие, что между городами a_i и b_i существует дорога на которую можно ввести налог в размере от l_i до r_i денежных единиц включительно.

Выведите единственное число — ответ на задачу по модулю 10⁹ + 7.