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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Vector;

public class ValidSets {
    
    public static void main(String[] args) throws IOException {
        ValidSetsSolver solver = new ValidSetsSolver();
        solver.read();
        solver.solve();
    }
}

class ValidSetsSolver {
    private final int MAXN = 2048;
    private final long MOD = 1000000007L;
    private InputReader input;
    private PrintWriter output;
    private int d, n;
    private Vector < Integer > [] v;
    private int[] a;
    private long[] dp;
    private boolean[] used;
    
    ValidSetsSolver() {
        input = new InputReader ( System.in );
        output= new PrintWriter ( System.out );
    }
    
    private void initialize() {
        a = new int[MAXN];
        v = new Vector[MAXN];
        dp = new long[MAXN];
        used = new boolean[MAXN];
        
        for ( int i = 1; i <= n; ++ i ) {
            v[i] = new Vector < Integer >();
        }
        
    }
    
    public void read() throws IOException {
        d = input.nextInt();
        n = input.nextInt();
        
        initialize();
        
        for ( int i = 1; i <= n; ++ i ) {
            a[i] = input.nextInt();
        }
        
        Integer x, y;
        
        for ( int i = 0; i < n - 1; ++ i ) {
            x = input.nextInt();
            y = input.nextInt();
            
            v[x].add(y);
            v[y].add(x);
        }
        
        input.close();
        
    }
    
    private long dfs ( int i, int root ) {
        int size = v[i].size();
        
        dp[i] = 1L;
        used[i] = true;
        
        for ( int j = 0; j < size; ++ j ) {
            int nextVertex = v[i].get(j);
            if ( a[nextVertex] < a[root] || a[root] < a[nextVertex] - d ) continue;
            if ( a[nextVertex] == a[root] && nextVertex < root ) continue;
            
            if ( used[ nextVertex ] == false ) {
                dp[i] *= ( dfs ( nextVertex, root ) + 1L );
                if ( dp[i] > MOD ) dp[i] %= MOD;
            }
        }
        
        return dp[i];
        
    }
    
    public void solve() {
        long answer = new Long(0);
        
        for ( int i = 1; i <= n; ++ i ) {
            resetArray();
            answer += dfs ( i, i );
            if ( answer > MOD ) answer %= MOD;
        }
        
        output.println ( answer );
        output.close();
        
    }
    
    private void resetArray() {
        for ( int i = 1; i <= n; ++ i ) {
            dp[i] = 0L;
            used[i] = false;
        }
    }
    
}

class InputReader {
        private BufferedReader input;
        private StringTokenizer tokenizer;
    
    public InputReader ( InputStream stream ) {
        input = new BufferedReader ( new InputStreamReader ( stream ), 32768 );
        tokenizer = null;
    }
    
    public void close() throws IOException {
        try {
            input.close();
        }
        catch ( IOException error ) {
            throw new RuntimeException ( error );
        }
    }

    public String next () {
        while ( tokenizer == null || !tokenizer.hasMoreTokens() ) {
            try {
                tokenizer = new StringTokenizer ( input.readLine() );
            }
            catch ( IOException error ) {
                throw new RuntimeException ( error );
            }
        }
        return tokenizer.nextToken();
    }
    
    public int nextInt() {
        return Integer.parseInt( next() );
    }
    
    public double nextDouble() {
        return Double.parseDouble ( next() );
    }
    
    public long nextLong() {
        return Long.parseLong( next() );
    }
    
    public String nextString() {
        return next();
    }
    
    public Boolean nextBool() {
        return Boolean.parseBoolean( next() );
    }
    
}