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.math.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

    final int MAXN = 2000 + 3;
    final int MODULO = 1000 * 1000 * 1000 + 7;
    
    int head[] = new int[MAXN], 
        next[] = new int[MAXN * 2], 
        to[] = new int[MAXN * 2];
    int a[] = new int[MAXN];
    
    boolean used[] = new boolean[MAXN];
    
    int gcnt = 1;
    
    void init() {
        gcnt = 1;
        fill(head, 0);
    }
    
    void addEdge(int u, int v) {
        next[gcnt] = head[u];
        head[u] = gcnt;
        to[gcnt++] = v;
    }
    
    long dfs(int u, int root, int d) {
        if (used[u]) return 0;
        
        if (!(a[root] <= a[u] && a[u]<=(a[root]+d))) return 0;
        
        if (a[u] == a[root] && u < root) return 0;
        
        used[u] = true;
        
        long c = 1;
        
        for (int i = head[u]; i > 0; i = next[i]) {
            int v = to[i];
            c *= (dfs(v, root, d)+1);
            c %= MODULO;
        }
        
        return c;       
    }
    
    void solve() throws IOException {
        int d = nextInt(),
            n = nextInt();
        
        for (int i = 0; i < n; i++) {
            a[i+1] = nextInt();
        }
        
        for (int i = 0; i < n-1; ++i) {
            int u = nextInt();
            int v = nextInt();
            addEdge(u, v);
            addEdge(v, u);
        }
        
        long res = 0;
        
        for (int i = 1; i <= n; ++i) {
            fill(used, false);
            long r = dfs(i, i, d);
            res = (r + res) % MODULO;
        }
        
        System.out.println(res);
    }

    int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }

    int modulo(int x, int y) {
        return (x % y + y) % y;
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    final String fileNameIn = "input.txt";
    final String fileNameOut = "output.txt";
    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");

    private void run() throws IOException {

        if (new File(fileNameIn).exists())
            in = new BufferedReader(new FileReader(fileNameIn));
        else
            in = new BufferedReader(new InputStreamReader(System.in));

        out = new PrintWriter(System.out);
        //      out = new PrintWriter(new FileWriter(fileNameOut));

        solve();

        in.close();
        out.close();
    }

    String nextToken() throws IOException {
        while (!st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextString() throws IOException {
        st = new StringTokenizer("");
        return in.readLine();
    }

    boolean EOF() throws IOException {
        while (!st.hasMoreTokens()) {
            String s = in.readLine();
            if (s == null)
                return true;
            st = new StringTokenizer(s);
        }
        return false;
    }
}