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:

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$ ($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$.

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.