题目描述

给定一个包含 $n$ 个节点的树。节点编号从 $1$ 到 $n$，编号为 $i(1 \le i \le n)$ 的节点的权值为 $a_i$。

你需要计算这棵树存在多少个 连通子图 满足如下条件：

该连通子图所包含的节点权值的最大值和最小值只差不超过 $d$。

由于满足条件的连通子图个数比较大，所以你只需要输出满足条件的连通子图个数模 $10^9+7$ 的结果即可。

输入格式

第一行，两个整数 $d(0 \le d \le 2000)$ 和 $n(1 \le n \le 2000)$，以一个空格分隔。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 2000)$。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n, u \neq v$），表示树上一条边对应的两个节点编号。

输出格式

输出满足条件的连通子图个数模 $10^9+7$ 的结果。

样例输入1

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

样例输出1

8

样例输入2

0 3
1 2 3
1 2
2 3

样例输出2

3

样例输入3

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

样例输出3

41

说明/提示

样例 1 解释

一共有 $8$ 个满足条件的连通子图，对应的节点集合分别为：

• $\{ 1 \}$
• $\{ 2 \}$
• $\{ 3 \}$
• $\{ 4 \}$
• $\{ 1, 2 \}$
• $\{ 1, 3 \}$
• $\{ 3, 4 \}$
• $\{ 1, 3, 4 \}$

数据规模与约定

• 对于 $30\%$ 的数据，$n,d,a_i \le 20$
• 对于 $60\%$ 的数据，$n,d,a_i \le 200$
• 对于 $100\%$ 的数据，$1 \le n,a_i \le 2000, 0 \le d \le 2000$