CF486D.Valid Sets

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:

1. S is non-empty.
2. 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.
3. .

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

众所周知，一个包含 $n$ 个节点和 $n-1$ 条边的无向连通图称为一棵树。现给定一个整数 $d$ 和一棵包含 $n$ 个节点的树。每个节点 $i$ 都有一个关联的值 $a_i$。

我们称树中的一组节点 $S$ 是合法的，当且仅当其满足以下条件：

1. $S$ 非空；
2. $S$ 是连通的。换言之，若节点 $u$ 和 $v$ 均属于 $S$，则 $u$ 与 $v$ 之间唯一简单路径上的所有节点也必须全部属于 $S$；
3. 。

你的任务是计算合法集合 $S$ 的总数。由于结果可能非常大，请输出其对 $1000000007$（即 $10^9 + 7$）取模后的余数。

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.

第一行包含两个用空格分隔的整数 $d$（$0 \le d \le 2000$）和 $n$（$1 \le n \le 2000$）。

第二行包含 $n$ 个用空格分隔的正整数 $a_1,\,a_2,\,...,\,a_n$（$1 \le a_i \le 2000$）。

接下来的 $n - 1$ 行，每行包含一对整数 $u$ 和 $v$（$1 \le u,\,v \le n$），表示节点 $u$ 与 $v$ 之间存在一条边。保证这些边构成一棵树。

Print the number of valid sets modulo 1000000007.

输出有效集合的数量对 $1000000007$ 取模的结果。

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.

在第一个样例中，恰好有 8 个有效集合：{1}、{2}、{3}、{4}、{1, 2}、{1, 3}、{3, 4} 和 {1, 3, 4}。集合 {1, 2, 3, 4} 无效，因为不满足第三个条件。集合 {1, 4} 满足第三个条件，但与第二个条件冲突。