Коров'ячий картинг#10351

Коров'ячий картинг

1 секунда

128 мегабайтів

Дуже складна

Бессі та фермер Джон захоплюються перегонами на козах. Це схоже на перегони на картингах, але замість картингів використовуються кози, а траса проходить через прилеглі сільськогосподарські угіддя. Угіддя складаються з $n$ лугів та $m$ доріг, кожна з яких з'єднує пару лугів.

Бессі планує створити кругову трасу на прилеглих фермах. Ферма - це підмножина з двох або більше лугів, де з кожного лугу можна дістатися до будь-якого іншого, використовуючи унікальну послідовність доріг.

На прилеглих сільськогосподарських угіддях може бути кілька ферм. Припустимо, вже існує $k$ ферм. Бессі хоче створити кругову трасу, з'єднавши всі $k$ ферм, додавши $k$ доріг довжини $x$ . Кожну ферму слід відвідати рівно один раз, і всередині кожної ферми необхідно пройти хоча б по одній дорозі.

Щоб траса була цікавою для гонщиків, її загальна довжина повинна бути не менше $y$ . Бессі хоче знати суму довжин усіх таких цікавих трас. Одна траса відрізняється від іншої, якщо на одній трасі є два сусідніх луги (після додавання доріг між фермами), але немає на іншій. Зверніть увагу, що мають значення лише вибрані дороги, а не напрямок, у якому по них будуть рухатися кози.

Вхідні дані

Перший рядок містить числа $n$ , $m$ , $x$ і $y$ ( $1 \leq n \leq 1500$ 1 \le n \le 1500, $1 \leq m \leq n - 1$ 1 \le m \le n - 1, $0 \leq x, y \leq 2500$ 0 \le x, y \le 2500). Кожен з $m$ наступних рядків описує дороги. Рядки мають вигляд $a_{i} b_{i} d_{i}$ a_i\ b_i\ d_i, що означає, що луги $a_{i}$ a_i і $b_{i}$ b_i з'єднані дорогою з довжиною $d_{i}$ d_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \le a_i, b_i \le n, $0 \leq d_{i} \leq 2500$ 0 \le d_i \le 2500). Кожен луг прилягає хоча б до однієї дороги, і серед доріг немає циклів.

Вихідні дані

Виведіть одне ціле число - суму довжин усіх цікавих трас. Оскільки сума довжин трас може бути досить великою, виведіть суму їх довжин за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

У цьому прикладі $6$ можливих трас

$1 \to 2 \to 4 \to 5 \to 1$ 1 \to 2 \to 4 \to 5 \to 1 (довжина $11$ )

$1 \to 2 \to 5 \to 4 \to 1$ 1 \to 2 \to 5 \to 4 \to 1 (довжина $11$ )

$2 \to 3 \to 4 \to 5 \to 2$ 2 \to 3 \to 4 \to 5 \to 2 (довжина $12$ )

$2 \to 3 \to 5 \to 4 \to 2$ 2 \to 3 \to 5 \to 4 \to 2 (довжина $12$ )

$1 \to 2 \to 3 \to 4 \to 5 \to 1$ 1 \to 2 \to 3 \to 4 \to 5 \to 1 (довжина $15$ )

$1 \to 2 \to 3 \to 5 \to 4 \to 1$ 1 \to 2 \to 3 \to 5 \to 4 \to 1 (довжина $15$ )

Підсумок дорівнює $12 + 12 + 15 + 15 = 54$ 12 + 12 + 15 + 15 = 54, де враховуються лише ті траси, довжина яких не менше $12$ .

Приклад 1