시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 5 3 3 60.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