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 a_{i} associated with it.

We call a set S of tree nodes valid if following conditions are satisfied: S is non-empty. 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. $\operatorname{max}_{u \in S} a_{u} - \operatorname{min}_{v \in S} a_{v} \leq d$.

Your task is to count the number of valid sets. Since the result can be very large, you must print its remainder modulo 1000000007 (10^9 + 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 a_1, a_2, ..., a_{n}(1 ≤ a_{i} ≤ 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.

Difficulty: interview

Starter code:

Solutions:
f = lambda: map(int, input().split())
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    u -= 1
    v -= 1
    p[u].append(v)
    p[v].append(u)

def g(u, x, a, b, q):
    k = 1
    for v in p[u]:
        if a < t[v] <= b or t[v] == a and v > q:
            if v != x: k += k * g(v, u, a, b, q) % m
    return k


s = 0
for q in range(n):
    a = t[q]
    b = a + d
    s += g(q, -1, a, b, q)

print(s % m)

f = lambda: map(int, input().split())
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)

f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: list(map(int, input().split()))
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)


f = lambda: map(int, input().split())
m = 1000000007

d, n = f()
t = list(f())
p = [[] for i in range(n)]
for j in range(n - 1):
    u, v = f()
    p[u - 1].append(v - 1)
    p[v - 1].append(u - 1)

def g(u, x, y):
    s = 1
    for v in p[u]:
        if 0 < t[v] - t[y] <= d or t[v] == t[y] and v > y:
            if v != x: s += s * g(v, u, y) % m
    return s

print(sum(g(y, -1, y) for y in range(n)) % m)

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()


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()


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()


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 = [0] + readInts()
    adj: list = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = readInts()
        adj[u].append(v)
        adj[v].append(u)

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

    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(1, n + 1):
        vis = [False for _ in range(n + 1)]
        f = [0 for _ in range(n + 1)]
        dfs(i, i)
        ans += f[i]
        ans %= MOD
    print(ans)


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


main()


mod=10**9+7
d,n=map(int,input().split())
a=[0]+list(map(int,input().split()))
tree=[[] for _ in range(n+1)]
for _ in range(n-1):
    u,v=map(int,input().split())
    tree[u].append(v)
    tree[v].append(u)

def dfs(u,root):
    visited[u]=True
    f[u]=1
    for i in tree[u]:
        if visited[i]==False:
            if a[i]<a[root] or a[i]>a[root]+d:continue
            if a[i]==a[root] and i<root: continue  
            dfs(i,root)                           
            f[u]=(f[u]*(f[i]+1))%(mod)
ans=0
for i in range(1,n+1):
    visited = [False] * (n+1)
    f = [0] * (n+1)
    dfs(i,i)
    ans=(ans+f[i])%mod
print(ans)

 
d, n = list(map(int,input().split()))
a = list(map(int, input().split()))

mas = [[] for _ in range(n+1)]

MOD = 1000000007
for _ in range(n-1):
    u, v = list(map(int,input().split()))
    mas[u].append(v)
    mas[v].append(u)    
    
# #mas = [[],[2,3,10],[1,6,7],[1],[7],[9],[2],[2,4,11],[9],[5,8,10],[1,9,12],[7],[10]]
# mas = [[],[2,3],[1],[1,4],[3]]
# a = [0,2,1,3,2]

# d = 1

# print('mas:',mas)
# print('a:',a)

k = 0
def dfs(nomer,mas,tyt_yge_bili,f,nach):
    nonlocal k
    f[nomer] = 1;
    # print(nomer ,"--", nach)
    tyt_yge_bili[nomer] = True
    # f.append(a[nomer-1])
    # # print(f)
    # if max(f)-min(f)<=d:
    #     k+=1
    #     print(f)
    for j in mas[nomer]:
        if tyt_yge_bili[j]!=True:
            if not ((a[j-1] < a[nach-1]) or (a[j-1] > a[nach-1] + d)) and not ((a[j-1] == a[nach-1]) and (j < nach)):
                dfs(j,mas,tyt_yge_bili,f,nach)
                # print(a[j-1],a[nach-1])
                f[nomer] = (f[nomer] * (f[j] + 1)) % MOD
            
rez = 0
for z in range(1,n+1):
    f = []
    tyt_yge_bili = []
    for _ in range(n+1):
        f.append(0)
        tyt_yge_bili.append(0)
    dfs(z,mas,tyt_yge_bili,f , z)
    rez = (rez + f[z]) % MOD

print(rez)





    


 
d, n = list(map(int,input().split()))
a = list(map(int, input().split()))

mas = [[] for _ in range(n+1)]

MOD = 1000000007
for _ in range(n-1):
    u, v = list(map(int,input().split()))
    mas[u].append(v)
    mas[v].append(u)    
    
# #mas = [[],[2,3,10],[1,6,7],[1],[7],[9],[2],[2,4,11],[9],[5,8,10],[1,9,12],[7],[10]]
# mas = [[],[2,3],[1],[1,4],[3]]
# a = [0,2,1,3,2]

# d = 1

# print('mas:',mas)
# print('a:',a)

k = 0
def dfs(nomer,mas,tyt_yge_bili,f,nach):
    nonlocal k
    f[nomer] = 1;
    # print(nomer ,"--", nach)
    tyt_yge_bili[nomer] = True
    # f.append(a[nomer-1])
    # # print(f)
    # if max(f)-min(f)<=d:
    #     k+=1
    #     print(f)
    for j in mas[nomer]:
        if tyt_yge_bili[j]!=True:
            if ((a[j-1] >= a[nach-1]) and (a[j-1] <= a[nach-1] + d)) and ((a[j-1] != a[nach-1]) or (j >= nach)):
                dfs(j,mas,tyt_yge_bili,f,nach)
                # print(a[j-1],a[nach-1])
                f[nomer] = (f[nomer] * (f[j] + 1)) % MOD
            
rez = 0
for z in range(1,n+1):
    f = []
    tyt_yge_bili = []
    for _ in range(n+1):
        f.append(0)
        tyt_yge_bili.append(0)
    dfs(z,mas,tyt_yge_bili,f , z)
    rez = (rez + f[z]) % MOD

print(rez)





    


 
d, n = list(map(int,input().split()))
a = list(map(int, input().split()))

mas = [[] for _ in range(n+1)]

MOD = 1000000007
for _ in range(n-1):
    u, v = list(map(int,input().split()))
    mas[u].append(v)
    mas[v].append(u) 


def dfs(nomer,mas,tyt_yge_bili,f,nach):
    f[nomer] = 1;
    tyt_yge_bili[nomer] = True
    for j in mas[nomer]:
        if tyt_yge_bili[j]!=True:
            if ((a[j-1] >= a[nach-1]) and (a[j-1] <= a[nach-1] + d)) and ((a[j-1] != a[nach-1]) or (j >= nach)):
                dfs(j,mas,tyt_yge_bili,f,nach)
                f[nomer] = (f[nomer] * (f[j] + 1)) % MOD
                
            
rez = 0
for z in range(1,n+1):
    f = []
    tyt_yge_bili = []
    for _ in range(n+1):
        f.append(0)
        tyt_yge_bili.append(0)
    dfs(z,mas,tyt_yge_bili,f , z)
    rez = (rez + f[z]) % MOD
    

print(rez)