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.*;
import java.math.*;
 
public class Main {
      
 
    int d, n;
    int[] val, visited;
    List<List<Integer>> adjList = new ArrayList<>();
    int mod = 1000000007;

    public long dfs(int node, int min, int max, int idx){

        visited[node] = 1;
        List<Integer> nbrs = adjList.get(node);
        long res = 1;

        for(int nbr : nbrs){
            if(val[nbr] < min 
              || val[nbr] > max 
              || (val[nbr] == min && idx < nbr) 
              || visited[nbr] == 1){
                continue;
            }

            res = (res * (dfs(nbr, min, max, idx) + 1)) % mod;
        }

        return res;
    }

    public void solve() throws IOException{

        d = in.nextInt();
        n = in.nextInt();

        val = new int[n + 1];
        adjList.add(new ArrayList<>());
        for(int i = 1; i <= n; i++){
            val[i] = in.nextInt();
            adjList.add(new ArrayList<>());
        }

        for(int i = 1; i <= n - 1; i++){
            int src = in.nextInt();
            int dst = in.nextInt();
            adjList.get(src).add(dst);
            adjList.get(dst).add(src);
        }

        long res = 0;

        for(int i = 1; i <= n; i++){
            visited = new int[n + 1];
            res = (res + dfs(i, val[i], val[i] + d, i)) % mod;
        }
    
        out.println(res);
    }
 


    FastScanner in;
    PrintWriter out;
 
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    class Pair{
        int x; int y;
        Pair(int ix, int iy){
            x = ix;
            y = iy;
        }
    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}
