Trong một lớp có \(n\) bạn và \(n - 1\) cặp bạ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ệ gián tiếp qua các cặp bạn trung gian này.

Qua một bài kiểm tra, cô giáo nhận thấy bạn thứ \(i\) đã làm được \(a_{i}\) bài của bài kiểm tra. Bằng một phép thần kỳ nào đó, không có hai bạn nào làm được cùng số lượng bài và mỗi bạn (trừ bạn chỉ làm được \(1\) bài) đều có ít nhất một người bạn trực tiếp làm được ít bài hơn.

Cô giáo muốn chấm điểm cho các bạn dựa trên thang điểm nguyên từ \(1 \rightarrow k\) sao cho không có hai bạn nào có cùng điểm. Sẽ rất bất công nếu như trong một cặp bạn trực tiếp, bạn này làm ít bài hơn nhưng lại nhận được điểm cao hơn.

Yêu cầu: Hãy tìm số cách chấm điểm hợp lý giúp cô giáo. Hay nói cách khác, gọi \(b_{i}\) là điểm của bạn thứ \(i\), cô giáo muốn tìm số cách chấm điểm sao cho với mọi cặp bạn trực tiếp gồm bạn \(i\) và bạn \(j\), nếu \(a_{i} > a_{j}\) thì \(b_{i} > b_{j}\) và ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 10^5, 1 \leq k \leq 10^9\)) lần lượt là số bạn và thang điểm của cô giáo.
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên \(i\) và \(j\) (\(1 \leq i, j \leq n, i \neq j\)) thể hiện một cặp bạn trực tiếp.
• Dòng cuối cùng chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n, a_i \neq a_j \ \forall i \neq j\)) là số bài làm được mỗi bạn.

Output

• 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ý của cô giáo khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k \leq 10\).
• Subtask \(2\) (\(20\%\) số diểm): \(k \leq 10^{2}\).
• Subtask \(3\) (\(20\%\) số điểm): \(k \leq 10^{3}\).
• Subtask \(4\) (\(20\%\) số điểm): \(k = n\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

1 4
1

4

3 4
1 2
1 3
1 2 3

8

5 5
1 2
2 3
3 4
4 5
1 2 3 4 5

1