13000번 - 홍준이와 가능한 집합

N개의 정점을 가진 트리가 있습니다. \(i\)번째 정점에는 가중치 \(a(i)\)가 부여되어 있습니다. 그리고 하나의 정수 d가 있을 때에, 다음 조건들을 만족하는 트리의 정점으로 구성된 집합 S를 ‘가능한 집합’이라고 합니다.

1. S는 공집합이 아닙니다.
2. S에 속하는 정점들은 연결되어 있습니다, 즉, S에 속하는 두 정점 u와 v에 대해 그 둘을 잇는 경로에 속하는 모든 정점들은 S에 속해야합니다.
3. \(max_{u \in S} {a_u} - min_{v \in S} {a_v} \le d\)

‘가능한 집합’ S의 경우의 수를 계산하는 프로그램을 작성하세요. 답이 매우 커질 수 있으므로 10⁹+7로 나눈 나머지 값을 출력하세요.

첫째 줄에 d와 N이 주어집니다. (0 ≤ d ≤ 20000, 1 ≤ N ≤ 20000)

둘째 줄에 \(a(i)\)를 나타내는 N개의 정수가 주어집니다. (1 ≤ \(a(i)\) ≤ 20000)

셋째 줄부터 N-1개의 줄에 걸쳐 트리의 간선을 나타내는 두 개의 정수 u와 v가 주어집니다.

문제의 답을 10⁹+7로 나눈 나머지를 출력합니다.

{1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {3, 4}, {1, 3, 4}