시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 2 2 100.000%

## 문제

You have a tree on $n$ vertices. Each vertex $v$ has weight $a_v$, and its degree is at most 5.

The density of a subset $S$ of vertices is the value

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

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

There are $2^n$ ways to choose $L$. How many such $L$ have their beauty no larger than $x$? As the answer can be very large, find it modulo 1 000 000 007.

## 입력

The input contains several test cases, and 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 number of vertices and the constraint on the beauty.

The next line contains $n$ integers $a_1, a_2, \dots , a_n$ ($0 \le a_i ≤ 35 000$): the weights of the tree vertices.

Each of the next $n − 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), describing an edge connecting vertices $u$ and $v$ in the tree.

It is guaranteed that the given graph is a tree. It is also guaranteed that each vertex has degree at most 5.

## 출력

For each test case, output a line containing a single integer: the number of ways to choose such a subset $L$ of tree vertices that the beauty of $L$ is no larger than $x$, modulo 1 000 000 007.

## 예제 입력 1

2
5 0
1 1 1 1 1
1 2
2 3
3 4
4 5
3 2
2 1 3
1 2
1 3


## 예제 출력 1

13
6