Dense Subgraph

You are given a tree with $n$ vertices. Each vertex $v$ has weight $a_v$, and every vertex has degree at most 5.

The density of a subset $S$ of vertices is

$\frac{\sum_{v \in S}{a_v}}{|S|}.$

Consider a subset $L$ of the tree vertices. The beauty of $L$ is the maximum density of a subset $S$ of $L$ that contains at least two vertices and induces a connected subgraph, or 0 if no such $S$ exists.

There are $2^n$ ways to choose $L$. How many of them have beauty at most $x$? Since the answer can be very large, print it modulo $1\,000\,000\,007$.

The first line contains a single integer $T$ ($1 \le T \le 30$), the number of test cases.

The first line of each test case contains two integers $n$ ($2 \le n \le 35\,000$) and $x$ ($0 \le x \le 35\,000$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 35\,000$).

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), an edge between vertices $u$ and $v$. The graph is guaranteed to be a tree, and each vertex has degree at most 5.

For each test case, print one line with the number of subsets $L$ whose beauty is at most $x$, modulo $1\,000\,000\,007$.