You are given a tree consisting of N nodes, each node i has a value a[i] (0 ≤ a[i] ≤ 1) associated with it.

We call a set S of tree nodes beautiful if following conditions are satisfied:

S is non-empty.
S is connected. In other words, if nodes u and v are in S, then all nodes lying on the simple path between u and v should also be presented in S.
Sum of all a[u] (u belong to S) equals to K where K is a given integer.

Your task is to count the number of beautiful sets. Since the answer may very large, you should print it modulo 10⁹ + 7.

Input

The first line contains one integer T - the number of test cases. Then T test cases follow.

Each test case consists of several lines.

The first line contains 2 integers N and K.
The second line contains N integers a[1], a[2], ..., a[N].
Then the next N - 1 line each contain pair of integers u and v (1 ≤ u, v ≤ N) denoting that there is an edge between u and v. It is guaranteed that these edges form a tree.

Output

For each test, print the answer in one line.

Constraints