Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Cho một đồ thị cây có N đỉnh N-1 cạnh, gốc của cây là đỉnh 1, mỗi đỉnh có một trọng số là A_i. Dễ dàng nhận thấy, ngoại trừ đỉnh 1, các đỉnh còn lại đều có một đỉnh cha và nhận nó làm đỉnh con. Từ mảng A người ta tiến hành xây dựng mảng P như sau:

P_u=A_u nếu như đỉnh u đó không có đỉnh con, ngược lại P_u=A_u*max(P_v1, P_v2...P_vm) với v₁,v₂...v_m lần lượt là các đỉnh con của u. Nhiệm vụ của bạn là tính P₁.

Input

• Dòng 1: Gồm một số nguyên N, số đỉnh của đồ thị (1<=N<=10⁵).
• Dòng 2: Gồm N số nguyên A₁ ... A_N với A_i là trọng số của đỉnh thứ i. (1<=A_i<=10⁹).
• N-1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v, tức là đỉnh u là cha đỉnh v. (1<=u,v<=N).

Output

• Một số nguyên duy nhất là P₁, do kết quả có thể rất lớn nên chỉ cần in ra phần dư cho 10⁹+7.

Example

Input:
3
1 2 3
1 2
1 3

Output:
3