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 C {
    public static void main (String[] args) {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        /*

        The first thing that was needed to solve this problem was the number of different connected
        subtrees rooted at some node n assuming all directions of the edges point away from the root.
        For any leaf node, the answer is 1 (it can only make a subtree rooted at itself)
        For any other node, the answer is the product of it's children plus 1. prod(a[v]+1) for all v
        This can be shown by looking at an example:
        Imagine that some node 1 connects to two other nodes 2 and 3, where the subtrees of 2 are:

        {2, 2 4, 2 5, 2 4 5}
        and the subtrees of 3 are:
        {3, 3 6}

        If we were to add 1 to all of these subsets, how many could we get? Well we can take each
        subset of two and connect it to each subset of three to get a total of 4*2 = 8 new subsets
        when connecting them through one. This is similar to if there were 3 nodes we were connecting
        to 1. It will just be the product of the number of sets of all the children of node 1.
        The plus one comes in here:
        instead of connecting the subsets of different children nodes, we can just insert 1 into each
        subset of its children (i.e. {1 2, 1 2 4, 1 2 5, 1 2 4 5} which gets us an extra a[v] nodes.

        So for this case, the total number of new subsets are:
        4 * 2 + 4 + 2 or
        (4+1)*(2+1)
        In a general case: (a[0]+1) * (a[1]+1) * (a[2]+1) ... * (a[v]+1)


        But then the problem of there being a maximum difference between sets comes in.
        Imagine for each node, we forced it to be the smallest value in all the subsets it
        could make. So when dfs-ing, we only search on the children of node n where the value of
        its child, v, is >= a[n] but is also <= a[n] + d and then run the same formula we got up there
        for each node.

        But this also over counts some subsets. Looking at the first sample case, if we were to make
        node 1 the smallest node in its subsets, it could connect to node 3 and then node 4. But when
        we're running our separate dfs on 4, 4 will connect to 3 and then to 1. But this set {1 3 4}
        was already counted when dfs-ing through 1. So to fix this, whenever the values of the root
        and the current child we're processing are the same, we should only dfs if the index of the child
        is either less than or greater than the index of the root (it shouldn't really matter which one
        you pick).

        Then just multiply under modulo for each node and add the result at the end.

         */

        d = fs.nextInt();
        int n = fs.nextInt();
        a = fs.nextIntArray(n);
        ArrayList<Integer>[] adj = new ArrayList[n];
        for(int i = 0; i < n; i++)
            adj[i] = new ArrayList<>();

        for(int i = 0; i < n-1; i++) {
            int u = fs.nextInt()-1, v = fs.nextInt()-1;
            adj[u].add(v);
            adj[v].add(u);
        }


        long res = 0;
        for(int i = 0; i < n; i++) {
            val = new long[n];
            V = new boolean[n];
            dfs(i, i, adj);
            res = (res + val[i]) % mod;
        }

        System.out.println(res%mod);

    }

    static int d, a[];
    static long val[], mod = (long)1e9+7;
    static boolean[] V;

    static void dfs (int at, int root, ArrayList<Integer>[] adj) {
        V[at] = true;
        val[at] = 1;
        for(Integer i : adj[at]) {
            if(V[i]) continue;
            if(a[i] < a[root] || a[i] > a[root] + d) continue;
            if(a[i] == a[root] && i > root) continue;
            dfs(i, root, adj);
            val[at] = ( ( val[at]%mod ) * ( (val[i]+1)%mod ) ) %mod;
        }
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
//                br = new BufferedReader(new FileReader("testdata.out"));
                st = new StringTokenizer("");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            String line = "";
            try {
                line = br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return line;
        }

        public Integer[] nextIntegerArray(int n) {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        public char[] nextCharArray() {
            return nextLine().toCharArray();
        }
    }
}