Tập hợp hợp lệ

Cho một cây vô hướng liên thông gồm $n$ đỉnh, mỗi đỉnh $i$ mang giá trị nguyên dương $a_i$. Cho thêm số nguyên không âm $d$.

Một tập hợp đỉnh $S$ của cây được gọi là hợp lệ nếu thoả mãn đồng thời:

1. $S$ khác rỗng.
2. $S$ liên thông trên cây — với hai đỉnh $u,v$ bất kỳ thuộc $S$, mọi đỉnh nằm trên đường đi đơn giữa $u$ và $v$ trong cây đều phải thuộc $S$.
3. ${max}_{v\in S}{a}_v-{min}_{v\in S}{a}_v\le d$.

Hãy đếm số tập hợp đỉ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$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $d$ và $n$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,\dots ,a_n$.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ mô tả một cạnh giữa hai đỉnh $u$ và $v$ của cây.

Dữ liệu ra

In ra một số nguyên duy nhất — số tập hợp đỉnh hợp lệ, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $0\le d\le 2000$
• $1\le n\le 2000$
• $1\le a_i\le 2000$
• $1\le u,v\le n$
• Dữ liệu đảm bảo các cạnh tạo thành một cây.

Ví dụ