你有一棵包含 $n$ 个顶点的树。每个顶点 $v$ 都有一个权重 $a_v$，且其度数不超过 5。

顶点子集 $S$ 的密度定义为： $$\frac{\sum_{v \in S} a_v}{|S|}$$

考虑树顶点的一个子集 $L$。$L$ 的“美观度”定义为满足以下条件的子集 $S$ 的最大密度：$S$ 是 $L$ 的子集，包含至少两个顶点，且构成一个连通导出子图；如果不存在这样的 $S$，则美观度为 0。

共有 $2^n$ 种选择 $L$ 的方式。有多少种这样的 $L$ 使得其美观度不超过 $x$？由于答案可能非常大，请输出其对 $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$)，描述树中连接顶点 $u$ 和 $v$ 的边。

保证给定的图是一棵树。同时保证每个顶点的度数不超过 5。

输出格式

对于每个测试用例，输出一行，包含一个整数：满足 $L$ 的美观度不超过 $x$ 的子集 $L$ 的选择方案数，对 $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