Giải bài trực tuyến

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ố không âm 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 v1,v2...vm lần lượt là các đỉnh con trực tiếp có cạnh nối với u. Nhiệm vụ của bạn là tính P₁.

Input

Dòng 1: Gồm một số nguyên N và M(1≤N≤10⁵, 1≤M≤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. (A_i≤10¹⁸).

N-1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v, thể hiện cạnh nối giữa u và 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 một số nguyên M 

Example

Input:
3 1000
1 2 3
1 2
1 3
Output:
3