Đường chạy

Alice sống ở một ngôi làng cổ, ngôi làng nổi tiếng với nhiều cảnh đẹp. Làng có \(n\) địa điểm được đánh số từ \(1\) đến \(n\) và có \(n - 1\) đoạn đường nối giữa các cặp địa điểm bảo đảm đi lại giữa hai địa điểm bất kì. Địa điểm \(i\) \((1 \leq i \leq n)\) có độ cao \(h_{i}\) so với mặt nước biển. Với tinh thần yêu thể thao, người dân trong lnagf thường tổ chức các vòng chạy, một vòng chạy được đặc trưng bởi một bộ ba số \(x, y, z\) \((1 \leq x < y < z \leq n)\), khi đó mọi người sẽ chạy theo đường đi ngắn nhất từ địa điểm \(x\) đến địa điểm \(y\), từ \(y\) đến \(z\) và cuối cùng là từ \(z\) về \(x\). ĐỘ dài đường đi ngắn nhất giữa hai địa điểm được tính bằng số đoạn đường ít nhất để đi từ địa điểm này đến địa điểm kia. Độ dài của một vòng chạy là tổng độ dài đường đi ngắn nhất từ \(x\) đến \(y\), từ \(y\) đến \(z\) và từ \(z\) về \(x\). Độ cao của một vòng chạy là độ cao của địa điểm có độ cao cao nhất trong các địa điểm thuộc vòng chạy (tính cả độ cao của các địa điểm \(x\), \(y\), \(z\)). Là một người yêu Tin học, với một giá trị \(t\), Aclie muốn tính tổng giá trị độ dài của tất cả các vòng chạy có độ cao vòng chạy là \(t\).

Yêu cầu: Gọi \(s\) là tổng giá trị độ dài các vòng chạy có độ cao vòng chạy là \(t\), hãy tính phần dư của \(s\) chia (\(10^9 + 7\)).

Input

Vào từ thiết bị vào chuẩn có dạng:

• Dòng đầu chứa hai số nguyên dương \(n, t\) \((n \leq 2 \times 10^5, t \leq 10^9)\).

• Dòng thứ hai gồm \(n\) số nguyên dương \(h_{1}, h_{2}, ..., h_{n}\) \((h_{i} \leq 10^9)\).

• Tiếp theo là \(n - 1\) dòng, mỗi dòng chứa hai số nguyên dương \(u\) và \(v\) \((1 \leq u, v \leq n; u \neq v)\) mô tả một đoạn đường nối giữa hai địa điểm \(u\) và \(v\).

Output

Ghi ra thiết bị ra chuẩn một số nguyên là phần dư của \(s\) chia \((10^9 + 7)\).

Example

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

50

Scoring

Subtask \(1\) (\(40\%\) số điểm) : \(n \leq 200\).

Subtask \(2\) (\(40\%\) số điểm) : \(t = 2\) và \(1 \leq h_{i} \leq 2\).

Subtask \(3\) (\(20\%\) số điểm) : Không có ràng buộc nào thêm