• Tên file bài làm: SCORING1.cpp
• File dữ liệu vào: SCORING1.INP
• File kết quả: SCORING1.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~).
• Mỗi bạn (ngoại trừ bạn chỉ làm được duy nhất 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ì thang điểm ~k~ trong bài này rất nhỏ (~k \le 10~), hãy giúp cô giáo đếm số cách chấm điểm hợp lý bằng thuật toán duyệt quay lui (hoặc sinh tổ hợp/hoán vị).

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 k \le 10~) lần lượt là số lượng học sinh và thang điểm tối đa.
• ~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 dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~, đôi một khác nhau) 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à số cách chấm điểm hợp lý thỏa mãn yêu cầu của cô giáo (chia dư cho ~10^9 + 7~, mặc dù với ~k \le 10~ đáp số không vượt quá kiểu nguyên thông thường).

Subtask

• Subtask 1 (100% số điểm): ~n \le k \le 10~.

Ví dụ

Giải thích ví dụ 1

• Có 3 bạn, thang điểm ~k = 4~. Số bài làm đúng: ~a_1 = 1, a_2 = 2, a_3 = 3~.
• Cặp bạn trực tiếp: (1, 2) và (1, 3). Do ~a_1 < a_2~ và ~a_1 < a_3~ nên điểm số phải thỏa ~b_1 < b_2~ và ~b_1 < b_3~.
• Có ~\binom{4}{3} = 4~ cách chọn bộ 3 điểm từ ~\{1, 2, 3, 4\}~.
• Với mỗi bộ 3 điểm phân biệt, điểm nhỏ nhất bắt buộc gán cho bạn 1 (~b_1~), hai điểm còn lại có thể gán tùy ý cho bạn 2 và bạn 3 (~2! = 2~ cách).
• Tổng số cách chấm điểm: ~4 \times 2 = 8~ cách.