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} \times~ ~max(P_{v_1}~, ~P_{v_2}~ ...~P_{v_m})~ với ~v_1, v_2 \dots v_m~ 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_{1}~.

Input

Dòng ~1~: Gồm một số nguyên ~N~ và ~M(1 \leq N \leq 10^{5}~, ~1 \leq M \leq 10^{18})~.

Dòng ~2~: Gồm ~N~ số nguyên ~A_{1}~ ...~A_{N}~ với ~A_{i}~ là trọng số của đỉnh thứ ~i~. ~(A_{i} \leq 10^{18})~.

~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 \leq u~, ~v \leq N)~.

Output

Một số nguyên duy nhất là ~P_{1}~, 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~

Sample Input

3 1000
1 2 3
1 2
1 3

Sample Output

3