Gán loại bảo mật cho cây

Một hệ thống gồm $n$ phòng được nối với nhau bởi $n-1$ hành lang sao cho từ phòng bất kỳ có thể đi tới mọi phòng khác, tức là hệ thống tạo thành một cây.

Mỗi phòng cần được gán một loại bảo mật là một số nguyên trong đoạn $[1,m]$. Các phòng có loại đúng bằng $k$ được gọi là phòng tối mật. Một cách gán loại cho tất cả các phòng được gọi là hợp lệ nếu thoả mãn đồng thời:

• Có nhiều nhất $x$ phòng tối mật.
• Với mọi phòng tối mật, tất cả các phòng kề nó (nối trực tiếp bằng một hành lang) phải có loại nhỏ hơn hẳn $k$. Nói riêng, hai phòng tối mật không được kề nhau.

Hãy đếm số cách gán loại hợp lệ, kết quả lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số phòng và số loại bảo mật.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$, $v_i$ mô tả một hành lang nối phòng $u_i$ và phòng $v_i$. Dữ liệu đảm bảo đồ thị tạo thành một cây.
• Dòng cuối chứa hai số nguyên $k$ và $x$: loại của phòng tối mật và số phòng tối mật tối đa.

Dữ liệu ra

Một số nguyên duy nhất: số cách gán loại hợp lệ, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le {10}^9$
• $1\le k\le m$
• $1\le x\le 10$
• $1\le u_i,v_i\le n$

Ví dụ