Một quốc gia có ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Các thành phố được kết nối bằng đúng ~n-1~ tuyến đường hai chiều. Hệ thống giao thông được xây dựng sao cho giữa hai thành phố bất kỳ luôn tồn tại duy nhất một đường đi. Nói cách khác, mạng lưới giao thông của quốc gia tạo thành một đồ thị dạng cây, mỗi tuyến đường nối trực tiếp hai thành phố không qua một thành phố trung gian nào cần đúng một ngày để đi qua.

Một đội công tác chuyên trách về kiểm định hạ tầng được giao nhiệm vụ đánh giá chất lượng của một dự án giao thông liên vùng, toàn bộ nhiệm vụ được chia thành ~m~ mức theo trình tự thực hiện, đánh số từ ~1~ đến ~m~. Thành phố thứ ~i~ có mức nhiệm vụ là ~a_i~. Trong đó, thành phố ~1~ có mức nhiệm vụ thấp nhất là ~1~, thành phố ~n~ có mức nhiệm vụ cao nhất là ~m~.

Một lộ trình hợp lệ là một lộ trình đi qua một dãy các thành phố ~u_1,u_2,\dots,u_m~ thỏa mãn đồng thời các điều kiện sau:

• ~u_1=1~ và ~u_m=n~.

• Với mỗi ~k~ từ ~2~ đến ~m-1~, thành phố ~u_k~ có nhiệm vụ mức ~k~.

• Đội công tác thực hiện nhiệm vụ xuất phát từ ~u_1~ lần lượt đi tới ~u_2,u_3,\dots,u_m~. Một chặng đường thực hiện nhiệm vụ đi từ thành phố ~u_i~ đến thành phố ~u_j~ được tính là hoàn thành khi ~u_j~ là điểm kết thúc của chặng đường đó với đường đi là ngắn nhất ~(1 \le i < j \le m)~. Việc đi ngang qua một thành phố trung gian nào đó trong lúc di chuyển giữa hai thành phố ~u_i~ và ~u_j~ không được tính là hoàn thành nhiệm vụ, kể cả khi thành phố đó có mức nhiệm vụ cao hơn.

Gọi ~d(u_i,u_j)~ là số ngày ít nhất để đi từ thành phố ~u_i~ tới thành phố ~u_j~, tức độ dài đường đi ngắn nhất giữa chúng trên cây. Thời gian hoàn thành của một lộ trình hợp lệ là tổng số ngày di chuyển của toàn bộ hành trình, cụ thể bằng:

~d(u_1,u_2)+d(u_2,u_3)+\dots+d(u_{m-1},u_m)~.

Yêu cầu: Hãy tính tổng thời gian hoàn thành của tất cả các lộ trình hợp lệ. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9+7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ ~(1 \le m \le n \le 10^5)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le m;\ a_1=1;\ a_n=m)~ tương ứng là mức nhiệm vụ của từng thành phố (dữ liệu đầu vào đảm bảo luôn tồn tại lộ trình hợp lệ);

• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x~ và ~y~ ~(1 \le x,y \le n)~ mô tả một tuyến đường nối hai thành phố ~x~ và ~y~.

Output

Gồm một số nguyên không âm là tổng thời gian hoàn thành của tất cả các lộ trình hợp lệ, lấy phần dư khi chia cho ~10^9+7~.

Scoring

Sample Input 1

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

Sample Output 1

24

Notes

Ở test ví dụ, với ~m=4~ ta có:

• Thành phố có mức nhiệm vụ ~1~ là ~\{1\}~;

• Thành phố có mức nhiệm vụ ~2~ là ~\{2,5\}~;

• Thành phố có mức nhiệm vụ ~3~ là ~\{3,4\}~;

• Thành phố có mức nhiệm vụ ~4~ là ~\{6\}~.

Nên mỗi lộ trình hợp lệ có dạng ~u_1=1~, tiếp đến ~u_2~ là một thành phố có mức nhiệm vụ ~2~, tiếp đến ~u_3~ là một thành phố có mức nhiệm vụ ~3~, cuối cùng ~u_4=6~. Các thành phố có mức nhiệm vụ ~2~ là ~2~ và ~5~, các thành phố có mức nhiệm vụ ~3~ là ~3~ và ~4~. Vậy có bốn lộ trình hợp lệ:

• ~1 \rightarrow 2 \rightarrow 3 \rightarrow 6~, thời gian hoàn thành ~d(1,2)+d(2,3)+d(3,6)=2+1+1=4~.

• ~1 \rightarrow 2 \rightarrow 4 \rightarrow 6~, thời gian hoàn thành ~d(1,2)+d(2,4)+d(4,6)=2+2+2=6~.

• ~1 \rightarrow 5 \rightarrow 3 \rightarrow 6~, thời gian hoàn thành ~d(1,5)+d(5,3)+d(3,6)=3+2+1=6~.

• ~1 \rightarrow 5 \rightarrow 4 \rightarrow 6~, thời gian hoàn thành ~d(1,5)+d(5,4)+d(4,6)=3+3+2=8~.

Vậy đáp án là ~4+6+6+8=24~.