Коров'ячий картинг
Бессі та фермер Джон захоплюються перегонами на козах. Це схоже на перегони на картингах, але замість картингів використовуються кози, а траса проходить через прилеглі сільськогосподарські угіддя. Угіддя складаються з n лугів та m доріг, кожна з яких з'єднує пару лугів.
Бессі планує створити кругову трасу на прилеглих фермах. Ферма - це підмножина з двох або більше лугів, де з кожного лугу можна дістатися до будь-якого іншого, використовуючи унікальну послідовність доріг.
На прилеглих сільськогосподарських угіддях може бути кілька ферм. Припустимо, вже існує k ферм. Бессі хоче створити кругову трасу, з'єднавши всі k ферм, додавши k доріг довжини x. Кожну ферму слід відвідати рівно один раз, і всередині кожної ферми необхідно пройти хоча б по одній дорозі.
Щоб траса була цікавою для гонщиків, її загальна довжина повинна бути не менше y. Бессі хоче знати суму довжин усіх таких цікавих трас. Одна траса відрізняється від іншої, якщо на одній трасі є два сусідніх луги (після додавання доріг між фермами), але немає на іншій. Зверніть увагу, що мають значення лише вибрані дороги, а не напрямок, у якому по них будуть рухатися кози.
Вхідні дані
Перший рядок містить числа n, m, x і y (1 ≤ n ≤ 1500, 1 ≤ m ≤ n − 1, 0 ≤ x, y ≤ 2500). Кожен з m наступних рядків описує дороги. Рядки мають вигляд a[i] b[i] d[i], що означає, що луги a[i] і b[i] з'єднані дорогою з довжиною d[i] (1 ≤ a[i], b[i] ≤ n, 0 ≤ d[i] ≤ 2500). Кожен луг прилягає хоча б до однієї дороги, і серед доріг немає циклів.
Вихідні дані
Виведіть одне ціле число - суму довжин усіх цікавих трас. Оскільки сума довжин трас може бути досить великою, виведіть суму їх довжин за модулем 10^9 + 7.
Приклад
У цьому прикладі 6 можливих трас
1 --> 2 --> 4 --> 5 --> 1 (довжина 11)
1 --> 2 --> 5 --> 4 --> 1 (довжина 11)
2 --> 3 --> 4 --> 5 --> 2 (довжина 12)
2 --> 3 --> 5 --> 4 --> 2 (довжина 12)
1 --> 2 --> 3 --> 4 --> 5 --> 1 (довжина 15)
1 --> 2 --> 3 --> 5 --> 4 --> 1 (довжина 15)
Підсумок дорівнює 12 + 12 + 15 + 15 = 54, де враховуються лише ті траси, довжина яких не менше 12.