Đua Xe Rừng

Có $N$ đỉnh và $M$ cạnh tạo thành một rừng (đồ thị không có chu trình), với $K=N-M$ cây. Mỗi cạnh có độ dài dương và mỗi đỉnh có ít nhất một cạnh nối.

Bessie muốn xây một vòng đua bằng cách:

• Chọn một đường đi (giữa hai đỉnh phân biệt) trong mỗi cây.
• Nối $K$ cây theo một thứ tự vòng tròn bằng $K$ cạnh mới, mỗi cạnh có độ dài $X$.

Tổng độ dài vòng đua = tổng độ dài $K$ đường đi + $K·X$. Hai vòng đua khác nhau nếu có hai đỉnh kề nhau ở vòng đua này nhưng không kề nhau ở vòng đua kia.

Hãy tính tổng độ dài của tất cả các vòng đua có tổng độ dài $\ge Y$, lấy kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: bốn số nguyên $N$, $M$, $X$, $Y$ ($1\le N\le 1500$, $1\le M\le N-1$, $0\le X,Y\le 2500$)
• $M$ dòng tiếp theo: mỗi dòng gồm $A_i$, $B_i$, $D_i$ (cạnh nối đỉnh $A_i$ và $B_i$ có độ dài $D_i\ge 1$)

Dữ liệu ra

Tổng độ dài tất cả các vòng đua hợp lệ, modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 1500$, $1\le M\le N-1$
• $0\le X,Y\le 2500$
• Đồ thị là rừng, mỗi đỉnh có ít nhất một cạnh nối

Ví dụ