План розміщення

Обмеження: 4 сек., 256 МіБ

Удома в Зеника та Марічки проведуть велику вечірку. Приїдуть їхні \(k\) друзів.

Тепер Зеник пробує знайти спосіб розмістити всіх друзів. Їхній будинок складається з \(n\) кімнат і \(n-1\) передпокою. Кожен передпокій з’єднує дві кімнати та має деяку довжину. З кожної кімнати можна дістатися до кожної через передпокої.

Зеник називає план розміщення добрим, якщо

• Кожен друг мешкає в якійсь кімнаті.

• Жодні двоє друзів не живуть в одній кімнаті.

• Існує кімната (неважливо, чи там хтось мешкає) така, що всі друзі можуть зустрітися в цій кімнаті, і відстань від неї до кімнати кожного з друзів не більша за \(l\).

Тепер Зеник хоче порахувати кількість добрих планів розміщення. Два плани вважаються різними, якщо хоча б один друг живе в різних кімнатах. Оскільки це число може бути дуже великим, виведіть його за модулем простого числа \(10^9+7\).

Вхідні дані

У першому рядку задано три цілі числа \(n\), \(k\) і \(l\).

Кожен із наступних \(n-1\) ряків містить три цілі числа \(a_i\), \(b_i\), \(c_i\), які означають, що є передпокій між кімнатами \(a_i\) та \(b_i\) з довжиною \(c_i\).

Вихідні дані

Виведіть одне число — кількість добрих планів розміщення за модулем \(10^9+7\).

Обмеження

\(1 \le k \le n \le 10^5\),

\(1 \le a_i, b_i \le n\),

\(1 \le c_i, l \le 10^9\).

Приклади