• Tên file bài làm: SCORING.cpp
• File dữ liệu vào: SCORING.INP
• File kết quả: SCORING.OUT
• Thời gian chạy: 1.0 giây

Đề bài

Trong một lớp học có ~n~ bạn học sinh và ~n - 1~ cặp bạn thân trực tiếp. Giữa hai bạn bất kỳ luôn tồn tại một mối quan hệ bạn bè trực tiếp hoặc gián tiếp thông qua các bạn trung gian (mối quan hệ tạo thành một đồ thị dạng cây gồm ~n~ đỉnh và ~n - 1~ cạnh).

Sau khi làm một bài kiểm tra, cô giáo nhận thấy bạn thứ ~i~ làm đúng được ~a_i~ bài. Điều đặc biệt là:

• Không có hai bạn nào làm được cùng số lượng bài (~a_i \ne a_j~ với mọi ~i \ne j~, và ~1 \le a_i \le n~).
• Mỗi bạn (ngoại trừ bạn chỉ làm được đúng 1 bài) đều có ít nhất một người bạn thân trực tiếp làm được ít bài hơn mình.

Cô giáo muốn chấm điểm cho các bạn dựa trên thang điểm số nguyên từ ~1~ đến ~k~ sao cho:

1. Không có hai bạn nào có cùng điểm số (~b_i \ne b_j~ với mọi ~i \ne j~, và ~1 \le b_i \le k~).
2. Sẽ rất bất công nếu trong một cặp bạn thân trực tiếp ~(i, j)~, bạn làm ít bài hơn lại nhận được điểm cao hơn. Do đó, với mọi cặp bạn thân trực tiếp ~i~ và ~j~, nếu ~a_i > a_j~ thì bắt buộc ~b_i > b_j~ và ngược lại.

Yêu cầu: Hãy tính số cách chấm điểm hợp lý giúp cô giáo. Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~1 \le n \le 10^5, 1 \le k \le 10^9, n \le k~) lần lượt là số lượng học sinh và thang điểm tối đa của cô giáo.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le n, u \ne v~) mô tả một cặp bạn thân trực tiếp.
• Dòng cuối cùng chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n, a_i \ne a_j \ \forall i \ne j~) là số lượng bài làm đúng của mỗi bạn.

Kết quả

• In ra một số nguyên duy nhất là phần dư của số cách chấm điểm hợp lý khi chia cho ~10^9 + 7~.

Subtask

• Subtask 1 (20% số điểm): ~k \le 10~.
• Subtask 2 (20% số điểm): ~k \le 100~.
• Subtask 3 (20% số điểm): ~k \le 1000~.
• Subtask 4 (20% số điểm): ~k = n~.
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm (~n \le 10^5, k \le 10^9~).

Ví dụ