Đất nước BTA có ~n~ thành phố và ~n - 1~ con đường, bảo đảm đi lại giữa tất cả các thành phố. Các thành phố được đánh số từ ~1~ đến ~n~, thành phố thứ ~i~ có nhu cầu sử dụng ~a_i~ viên kim cương. Chính phủ muốn cấp phát kim cương cho tất cả các thành phố bằng cách dịch chuyển các viên kim cương. Theo đó, có một hành trình bất kì gồm các thành phố, bắt đầu từ thành phố ~1~. Ban đầu chỉ có cổng du hành ở thành phố ~1~. Mỗi lần đến một thành phố, chính phủ được phép lựa chọn một trong hai hành động:

• Khai thác một viên kim cương và dịch chuyển đến một thành phố đã có sẵn cổng du hành.
• Hoặc xây dựng một cổng du hành mới ở một thành phố bất kì mà kề với ít nhất một thành phố đã có cổng du hành.

Hãy đếm số dãy thao tác khác nhau để cấp phát kim cương cho tất cả các thành phố, sao cho số thao tác là ít nhất có thể. Hai dãy thao tác được gọi là khác nhau nếu tồn tại một thời điểm mà loại hành động được chọn ở hai dãy là khác nhau, hoặc cùng chọn một loại hành động nhưng áp dụng với hai thành phố khác nhau.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương $n$ $(1 \leq n \leq 10^5)$.
• Dòng tiếp theo chứa $n$ số nguyên không âm: ~a_1, a_2, \dots, a_n~.
• Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên mô tả một cạnh của cây.
• Dữ liệu đảm bảo tổng các $a_i$ không vượt quá $10^6$.

Dữ liệu ra

Ghi một số nguyên duy nhất là số dãy thao tác khác nhau, sau khi chia lấy dư cho $10^9+7$.

Ví dụ

Đầu vào

4
1 0 2 0
1 2
2 3
1 4

Đầu ra

5

Giải thích

Các dãy VD đầu tiên là: $12333, 21333, 23133, 23313, 23331$ (theo thứ tự xuất hiện của các đỉnh, nếu chưa xây dựng cổng du hành thì là thao tác loại $2$, ngược lại là thao tác loại $1$).

Tính điểm

• Subtask $1$ $(30\%$ số điểm$)$: $1 \leq n \leq 1000$, tổng các $a_i$ không quá $1000$.
• Subtask $2$ $(70\%$ số điểm$)$: Không có ràng buộc gì thêm.