Kiosks

Một trung tâm mua sắm có \(n\) ki-ốt được đánh số từ \(1\) đến \(n\).
Ki-ốt \(i\) bán một mặt hàng có mã \(c_i\).

Giữa các ki-ốt có \(n-1\) con đường hai chiều; con đường thứ \(j\) nối giữa hai ki-ốt \(u_j\) và \(v_j\).
Hệ thống đường đi đảm bảo luôn có đường đi giữa mọi cặp ki-ốt (tức là đồ thị là một cây).

Trong thời kỳ dịch bệnh, siêu thị muốn tạm ngưng hoạt động một số ki-ốt.
Khi một ki-ốt bị ngưng hoạt động, tất cả các con đường nối tới ki-ốt đó cũng bị chặn.
Gọi tập các ki-ốt còn hoạt động là \(S\).

Một phương án được xem là hợp lệ nếu thỏa mãn đồng thời:

• Các ki-ốt trong \(S\) liên thông với nhau (tức đồ thị cảm ứng bởi \(S\) là liên thông).
• Với mọi mã hàng \(t\) từ \(1\) đến \(k\), tồn tại ít nhất một ki-ốt còn hoạt động có \(c_i=t\).

Hai phương án được gọi là khác nhau nếu tồn tại một ki-ốt thuộc \(S\) trong phương án này nhưng không thuộc \(S\) trong phương án kia.

Yêu cầu. Hãy đếm số phương án hợp lệ, in ra phần dư khi chia cho \(10^9+7\).

\InputFile

• Dòng đầu chứa hai số nguyên dương \(n, k\) \((1 \le n \le 10^4,\ 1 \le k \le 10)\).
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\) \((1 \le c_i \le n)\).
• \(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)\) mô tả một con đường hai chiều.

\OutputFile

• In ra một số nguyên là số phương án hợp lệ modulo \(10^9+7\).

\Examples
\beginexample
\exmp
4 3
1 2 4 3
1 2
2 3
3 4

1

\endexample

\Note
Vì các ki-ốt còn hoạt động phải liên thông nên tập \(S\) luôn là một cây con liên thông của cây ban đầu.
Điều kiện còn lại yêu cầu các mặt hàng từ \(1\) đến \(k\) đều xuất hiện ít nhất một lần trong \(S\).

\Scoring

• (30%) Subtask 1: \(k = 1\);
• (30%) Subtask 2: Mỗi ki-ốt có bậc không quá \(2\);
• (40%) Subtask 3: Không có ràng buộc bổ sung.

\endproblem