human
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. .


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.
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python program to print the number of valid sets modulo 1000000007.

import sys

def readInts(): return [int(x) for x in sys.stdin.readline().split()]

def readInt(): return int(sys.stdin.readline())

# def print(x):
    # sys.stdout.write(str(x) + '\n')

def solve():
    MOD = int(1e9 + 7)
    d, n = readInts()
    a = readInts()
    adj: list = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = readInts()
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)

    vis = [False for _ in range(n)]
    f = [0 for _ in range(n)]

    def dfs(cur, root):
        vis[cur] = True

        f[cur] = 1
        for neigh in adj[cur]:
            if vis[neigh]:
                continue
            if not (a[root] <= a[neigh] <= a[root] + d):
                continue
            if a[neigh] == a[root] and neigh < root:
                continue
            dfs(neigh, root)
            f[cur] *= f[neigh] + 1
            f[cur] %= MOD

    ans = 0
    for i in range(0, n):
        vis = [False for _ in range(n)]
        f = [0 for _ in range(n)]
        dfs(i, i)
        ans += f[i]
        ans %= MOD
    print(ans)

def main():
    t = 1
    # t = readInt()
    for _ in range(t):
        solve()

main()