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 static java.lang.System.exit;
import static java.util.Arrays.fill;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Locale;
import java.util.StringTokenizer;

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

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");

    private void run() throws IOException {
        if (new File("input.txt").exists())
            in = new BufferedReader(new FileReader("input.txt"));
        else
            in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        in.close();
        out.close();
    }

    final long MOD = 1000L * 1000L * 1000L + 7L;

    int N = 2001;
    int M = 5002;
    int D = 2001;

    int head[] = new int[N];
    int next[] = new int[M];
    int to[] = new int[M];
    int cnt = 0;
    boolean inuse[] = new boolean[N];

    long a[] = new long[N];

    long l[] = new long[N];
    long r[] = new long[N];

    int d = 0;
    int n = 0;

    long ans = 0;

    private void solve() throws IOException {

        d = nextInt();
        n = nextInt();

        for (int i = 0; i < n; i++)
            a[i] = nextInt();

        fill(head, -1);

        for (int i = 0; i < n - 1; i++)
            add(nextInt() - 1, nextInt() - 1);

        ans = 0;

        for (int i = 0; i < D; i++) {
            for (int j = 0; j < n; j++) {
                l[j] = (a[j] == i) ? 1L : 0L;
                r[j] = (a[j] > i && a[j] <= i + d) ? 1L : 0L;
            }
            dfs(0, i);
        }
        
        out.println(ans);
    }

    void dfs(int u, int c) {
        inuse[u] = true;
        
        for (int i = head[u]; i > -1; i = next[i])
            if (!inuse[to[i]])
                dfs(to[i], c);

        for (int i = head[u]; i > -1; i = next[i])
            if (!inuse[to[i]]) {
                int v = to[i];
                long nl = (l[u] + (l[v] * (l[u] + r[u])));
                nl %= MOD;
                nl += r[v] * l[u];
                nl %= MOD;
                long nr = (r[u] + r[v] * r[u]) % MOD;
                l[u] = nl;
                r[u] = nr;
            }

//      System.err.println(u + " " + l[u] + " " + c);
        ans += l[u];
        ans %= MOD;
        inuse[u] = false;
    }

    void add(int u, int v) {
        next[cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt++;

        next[cnt] = head[v];
        to[cnt] = u;
        head[v] = cnt++;
    }

    void chk(boolean b) {
        if (b)
            return;
        System.out.println(new Error().getStackTrace()[1]);
        exit(999);
    }

    void deb(String fmt, Object... args) {
        System.out.printf(Locale.US, fmt + "%n", args);
    }

    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 nextLine() 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;
    }
}
