밀집 부분 그래프

정점이 $n$개인 트리가 주어진다. 각 정점 $v$에는 가중치 $a_v$가 있고, 모든 정점의 차수는 최대 5이다.

정점 집합 $S$의 밀도는 다음과 같이 정의한다.

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

트리의 정점 집합 $L$을 생각한다. $L$의 아름다움은 $L$의 부분집합 $S$ 중 정점을 두 개 이상 포함하고 유도 부분 그래프가 연결된 것들의 밀도 최댓값이다. 그런 $S$가 없으면 아름다움은 0이다.

$L$을 고르는 방법은 $2^n$가지이다. 아름다움이 $x$ 이하인 $L$은 몇 개인지 구하라. 답이 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 30$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$ ($2 \le n \le 35\,000$)과 $x$ ($0 \le x \le 35\,000$)가 주어진다.

다음 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 35\,000$)이 주어진다.

이어서 $n-1$개의 줄에 정점 $u$와 $v$ ($1 \le u, v \le n$)를 잇는 간선이 하나씩 주어진다. 주어지는 그래프는 트리이며, 각 정점의 차수는 최대 5이다.

각 테스트 케이스마다 아름다움이 $x$ 이하인 부분 집합 $L$의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.