Bessie và Farmer John thích đua xe dê kéo. Ý tưởng rất giống với đua Go-Kart mà những người khác yêu thích, chỉ khác là xe được dê kéo và đường đua được tạo từ vùng đất nông nghiệp gần đó. Vùng đất này gồm \(N\) đồng cỏ và \(M\) con đường, mỗi con đường nối một cặp đồng cỏ.

Bessie muốn tạo một đường đua từ các trang trại gần đó. Một trang trại là một tập con gồm ít nhất hai đồng cỏ, trong đó từ mỗi đồng cỏ đều có thể đến mọi đồng cỏ khác theo một dãy đường duy nhất.

Vùng đất nông nghiệp gần đó có thể chứa nhiều trang trại. Giả sử có \(K\) trang trại. Bessie muốn tạo một vòng đua xe dê kéo bằng cách kết nối cả \(K\) trang trại, bổ sung \(K\) con đường có độ dài \(X\). Mỗi trang trại phải được ghé thăm đúng một lần và phải đi qua ít nhất một con đường bên trong mỗi trang trại.

Để đường đua thú vị đối với các tay đua, tổng chiều dài đường đua phải ít nhất là \(Y\). Bessie muốn biết tổng chiều dài của tất cả các đường đua thú vị như vậy. Hai đường đua được xem là khác nhau nếu tồn tại hai đồng cỏ kề nhau (sau khi bổ sung các con đường giữa những trang trại) trong một đường đua nhưng không kề nhau trong đường đua kia. Lưu ý rằng chỉ những con đường được chọn mới quan trọng, không quan trọng hướng mà xe dê kéo sẽ di chuyển trên các con đường đó.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\), \(X\) và \(Y\), trong đó \(1 \leq N \leq 1500\), \(1 \leq M \leq N-1\) và \(0 \leq X, Y \leq 2500\).

Mỗi dòng trong \(M\) dòng tiếp theo mô tả một con đường. Các dòng có dạng \(A_i\) \(B_i\) \(D_i\), nghĩa là đồng cỏ \(A_i\) và đồng cỏ \(B_i\) được nối bởi một con đường có độ dài nguyên \(D_i\) (\(1 \leq A_i, B_i \leq N\), \(0 \leq D_i \leq 2500\)). Mỗi đồng cỏ là đầu mút của ít nhất một con đường, và hệ thống đường không có chu trình.

Phân nhóm

Trong ít nhất 70% số test, dữ liệu còn bảo đảm \(N \leq 1000\) và \(Y \leq 1000\).

Dữ liệu ra

In ra một số nguyên duy nhất là tổng chiều dài của tất cả các đường đua thú vị. Vì tổng chiều dài có thể rất lớn, hãy in tổng này theo modulo \(10^9+7\).

Ví dụ

5 3 1 12
1 2 3
2 3 4
4 5 6

54

Lưu ý rằng đối với bài này, giới hạn thời gian tiêu chuẩn được tăng lên 3 giây cho mỗi test (6 giây cho mỗi test đối với Java và Python).

Nguồn

USACO 2019 February Contest, Platinum — Moorio Kart

Tác giả: Matt Fontaine.