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 ai 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. <image>.



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).

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 a1, a2, ..., an(1 ≤ ai ≤ 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.
import java.io.*;
import java.util.*;

public class CF486D {
	static final long MD = 1000000007;
	static class Vertex implements Comparable<Vertex> {
		int a, i;
		boolean used = false;
		List<Vertex> list = new ArrayList<>();
		Vertex(int a, int i) {
			this.a = a;
			this.i = i;
		}
		@Override public int compareTo(Vertex v) {
			return a != v.a ? a - v.a : i - v.i;
		}
		long dfs(Vertex u, int max) {
			long cnt = 1;
			for (Vertex v : list) {
				if (v == u || v.used || v.a > max)
					continue;
				cnt = cnt * (v.dfs(this, max) + 1) % MD;
			}
			return cnt;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int d = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		Vertex[] vv = new Vertex[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			int a = Integer.parseInt(st.nextToken());
			vv[i] = new Vertex(a, i);
		}
		for (int k = 0; k < n - 1; k++) {
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken()) - 1;
			int j = Integer.parseInt(st.nextToken()) - 1;
			vv[i].list.add(vv[j]);
			vv[j].list.add(vv[i]);
		}
		Arrays.sort(vv);
		long sum = 0;
		for (int i = 0; i < n; i++) {
			long cnt = vv[i].dfs(null, vv[i].a + d);
			sum = (sum + cnt) % MD;
			vv[i].used = true;
		}
		System.out.println(sum);
	}
}
