As you know, an undirected connected graph with n nodes and n - 1 edges is called a tree. You are given an integer d and a tree consisting of n nodes. Each node i has a value a_{i} associated with it.

We call a set S of tree nodes valid if following conditions are satisfied: S is non-empty. S is connected. In other words, if nodes u and v are in S, then all nodes lying on the simple path between u and v should also be presented in S. $\operatorname{max}_{u \in S} a_{u} - \operatorname{min}_{v \in S} a_{v} \leq d$.

Your task is to count the number of valid sets. Since the result can be very large, you must print its remainder modulo 1000000007 (10^9 + 7).


-----Input-----

The first line contains two space-separated integers d (0 ≤ d ≤ 2000) and n (1 ≤ n ≤ 2000).

The second line contains n space-separated positive integers a_1, a_2, ..., a_{n}(1 ≤ a_{i} ≤ 2000).

Then the next n - 1 line each contain pair of integers u and v (1 ≤ u, v ≤ n) denoting that there is an edge between u and v. It is guaranteed that these edges form a tree.


-----Output-----

Print the number of valid sets modulo 1000000007.


-----Examples-----
Input
1 4
2 1 3 2
1 2
1 3
3 4

Output
8

Input
0 3
1 2 3
1 2
2 3

Output
3

Input
4 8
7 8 7 5 4 6 4 10
1 6
1 2
5 8
1 3
3 5
6 7
3 4

Output
41



-----Note-----

In the first sample, there are exactly 8 valid sets: {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {3, 4} and {1, 3, 4}. Set {1, 2, 3, 4} is not valid, because the third condition isn't satisfied. Set {1, 4} satisfies the third condition, but conflicts with the second condition.

Difficulty: HARD
Tags: Tree algorithms

Dynamic programming

Graph traversal

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
f = lambda : map(int, input().split())
m = 1000000007
(d, n) = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
	(u, v) = f()
	p[u - 1].append(v - 1)
	p[v - 1].append(u - 1)

def g(u, x, y):
	s = 1
	for v in p[u]:
		if 0 < t[v] - t[y] <= d or (t[v] == t[y] and v > y):
			if v != x:
				s += s * g(v, u, y) % m
	return s
print(sum((g(y, -1, y) for y in range(n))) % m)


(d, n) = map(int, input().split())
a = list(map(int, input().split()))
mas = [[] for _ in range(n + 1)]
MOD = 1000000007
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	mas[u].append(v)
	mas[v].append(u)
k = 0

def dfs(nomer, mas, tyt_yge_bili, f, nach):
	global k
	f[nomer] = 1
	tyt_yge_bili[nomer] = True
	for j in mas[nomer]:
		if tyt_yge_bili[j] != True:
			if (a[j - 1] >= a[nach - 1] and a[j - 1] <= a[nach - 1] + d) and (a[j - 1] != a[nach - 1] or j >= nach):
				dfs(j, mas, tyt_yge_bili, f, nach)
				f[nomer] = f[nomer] * (f[j] + 1) % MOD
rez = 0
for z in range(1, n + 1):
	f = []
	tyt_yge_bili = []
	for _ in range(n + 1):
		f.append(0)
		tyt_yge_bili.append(0)
	dfs(z, mas, tyt_yge_bili, f, z)
	rez = (rez + f[z]) % MOD
print(rez)


(d, n) = map(int, input().split())
M = 10 ** 9 + 7
a = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
vis = [0] * n

def dfs(i, prev, j):
	s = 1
	for v in g[i]:
		if 0 < a[v] - a[j] <= d or (a[v] == a[j] and v > j):
			if v != prev:
				s += s * dfs(v, i, j) % M
	return s
print(sum((dfs(i, -1, i) for i in range(n))) % M)


f = lambda : map(int, input().split())
m = 1000000007
(d, n) = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
	(u, v) = f()
	u -= 1
	v -= 1
	p[u].append(v)
	p[v].append(u)

def g(u, x, a, b, q):
	k = 1
	for v in p[u]:
		if a < t[v] <= b or (t[v] == a and v > q):
			if v != x:
				k += k * g(v, u, a, b, q) % m
	return k
s = 0
for q in range(n):
	a = t[q]
	b = a + d
	s += g(q, -1, a, b, q)
print(s % m)


mod = 10 ** 9 + 7
(d, n) = map(int, input().split())
a = [0] + list(map(int, input().split()))
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	tree[u].append(v)
	tree[v].append(u)

def dfs(u, root):
	visited[u] = True
	f[u] = 1
	for i in tree[u]:
		if visited[i] == False:
			if a[i] < a[root] or a[i] > a[root] + d:
				continue
			if a[i] == a[root] and i < root:
				continue
			dfs(i, root)
			f[u] = f[u] * (f[i] + 1) % mod
ans = 0
for i in range(1, n + 1):
	visited = [False] * (n + 1)
	f = [0] * (n + 1)
	dfs(i, i)
	ans = (ans + f[i]) % mod
print(ans)


import sys

def readInts():
	return [int(x) for x in sys.stdin.readline().split()]

def readInt():
	return int(sys.stdin.readline())

def print(x):
	sys.stdout.write(str(x) + '\n')

def solve():
	MOD = int(1000000000.0 + 7)
	(d, n) = readInts()
	a = readInts()
	adj: list = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = readInts()
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	vis = [False for _ in range(n)]
	f = [0 for _ in range(n)]

	def dfs(cur, root):
		vis[cur] = True
		f[cur] = 1
		for neigh in adj[cur]:
			if vis[neigh]:
				continue
			if not a[root] <= a[neigh] <= a[root] + d:
				continue
			if a[neigh] == a[root] and neigh < root:
				continue
			dfs(neigh, root)
			f[cur] *= f[neigh] + 1
			f[cur] %= MOD
	ans = 0
	for i in range(0, n):
		vis = [False for _ in range(n)]
		f = [0 for _ in range(n)]
		dfs(i, i)
		ans += f[i]
		ans %= MOD
	print(ans)

def main():
	t = 1
	for _ in range(t):
		solve()
main()