Một trung tâm mua sắm có \(n\) kiốt (kiosk) đánh số từ \(1\) tới \(n\), kiốt thứ \(i\) bán mặt hàng \(c[i]\).

Siêu thị có \(n-1\) con đường hai chiều đánh số từ \(1\) đến \(n-1\), con đường thứ \(i\) nối giữa kiốt \(u[i]\) và \(v[i]\). Hệ thống các con đường đảm bảo sự đi lại giữa hai kiốt bất kỳ.

Trong thời kỳ dịch bệnh, người ta muốn ngưng hoạt động một số kiốt để dễ dàng kiểm soát các hoạt động mua bán cũng như giao tiếp với khách hàng.
Khi một kiốt bị ngừng hoạt động, tất cả các con đường nối tới kiốt đó đều bị chặn để đảm bảo an ninh.

Tuy nhiên, để không ảnh hưởng tới khách hàng, siêu thị muốn lập phương án sao cho các kiốt còn hoạt động phải thỏa mãn hai điều kiện sau:

1. Các kiốt còn hoạt động phải liên thông với nhau:
   Tức là giữa hai kiốt bất kỳ vẫn còn mở cửa phải tồn tại đường đi thông qua các con đường không bị chặn.

2. Tất cả các mặt hàng mang số hiệu từ \(1\) tới \(k\) (là những mặt hàng thiết yếu) đều phải có bán ở ít nhất một kiốt còn hoạt động.

Hai phương án được gọi là khác nhau nếu tồn tại ít nhất một kiốt bị ngừng hoạt động trong một phương án nhưng vẫn được hoạt động trong phương án còn lại.

Yêu cầu

• Cho biết có bao nhiêu phương án khác nhau thỏa mãn điều kiện trên.
  In ra số dư trong phép chia kết quả cho \(1000000007\) (tức \(10^9 + 7\)).

Dữ liệu vào

• Dòng 1: Hai số nguyên \(n\), \(k\) \((1 \le n \le 10^4, 1 \le k \le 10)\)
• Dòng 2: \(n\) số nguyên \(c[1], c[2], ..., 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[i]\), \(v[i]\), thể hiện một con đường nối hai kiốt.

Dữ liệu ra

• Một số nguyên duy nhất — là số phương án hợp lệ modulo \(1000000007\).

Ràng buộc

• Subtask 1 (30% số điểm): \(k = 1\)
• Subtask 2 (30% số điểm): Mỗi kiốt có không quá 2 con đường nối tới nó (cây là một chuỗi).
• Subtask 3 (40% số điểm): Không có ràng buộc bổ sung.

Input 1

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

Output 1

1

Input 2

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

Output 2

11