如您所知,具有 n 个节点和 n - 1 个边的无向连通图称为树。给定一个整数 d 和一棵由 n 个节点组成的树。每个节点 i 都有一个与其关联的值 ai 。
如果满足以下条件,我们称树节点集合 S 有效:
1. S 非空。
2. S 已连接。换句话说,如果节点 u 和 v 在 S 中,那么位于 u 和 v 之间的简单路径上的所有节点也应该出现在 S 中。
3. $$\max_{u \in S} a_u - \min_{v \in S} a_v \leq d$$。
您的任务是计算有效组的数量。由于结果可能非常大,因此必须打印其模 1000000007 (109 + 7) 的余数。
输入
第一行包含两个以空格分隔的整数 d (0 ≤ d ≤ 2000) 和 n (1 ≤ n ≤ 2000)。
第二行包含 n 个空格分隔的正整数 a1, a2, ..., an(1 ≤ ai ≤ 2000)。
那么接下来的 n - 1 行每行包含一对整数 u 和 v (1 ≤ u, v ≤ n) 表示 u 和 v 之间有一条边。保证这些边形成一棵树。
输出
打印以 1000000007 为模的有效组数。
示例
输入 #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
注意
在第一个示例中,正好有 8 个有效集合:{1}、{2}、{3}、{4}、{1, 2}、{1, 3}、{3, 4} 和 {1, 3, 4}。集合 {1, 2, 3, 4} 无效,因为不满足第三个条件。集合{1, 4}满足第三个条件,但与第二个条件冲突。