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.util.*;
import java.io.*;

public class d {
   public static ArrayList<Integer>[] adj;
   public static boolean[] valid;
   public static int[] value;
   public static int d;
   public static int MOD = 1000000007;
   public static void main(String[] Args) {
      Scanner sc = new Scanner(System.in);
      d = sc.nextInt();
      int n = sc.nextInt();
      adj = new ArrayList[n];
      for (int i = 0; i < n; i++)
         adj[i] = new ArrayList<Integer>();
      Pair[] ps = new Pair[n];
      value = new int[n];
      for (int i = 0; i < n; i++) {
         ps[i] = new Pair(sc.nextInt(), i);
         value[i] = ps[i].v;
      }
      Arrays.sort(ps);
      for (int i = 0; i < n - 1; i++) {
         int a = sc.nextInt() - 1;
         int b = sc.nextInt() - 1;
         adj[a].add(b);
         adj[b].add(a);
      }
      valid = new boolean[n];
      Arrays.fill(valid, true);
      long ans = 0;
      for (int i = 0; i < n; i++) {
         root = ps[i].i;
         ans += DFS(ps[i].i, -1);
         valid[ps[i].i] = false;
      }
      System.out.println(ans%MOD);
   }
   
   public static int root;
   public static long DFS(int cur, int p) {
      long ans = 1;
      for (Integer x : adj[cur])
         if (valid[x] && x != p && value[x] <= value[root] + d) {
            ans *= (1 + DFS(x, cur));
            ans %= MOD;
         }
      return ans;
   }
   
   public static class Pair implements Comparable<Pair> {
      int v, i;
      Pair(int vv, int ii) {
         v = vv;
         i = ii;
      }
      public int compareTo(Pair o) {
         return v - o.v;
      }
   }
}