You are given a tree consisting of n nodes, each node i has a value ai (0 ≤ ai ≤ 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 au (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 109 + 7.

Input

The first line contains the number of test cases t. Then t test cases follow. Each test case consists of several lines:

• The first line contains two integers n (1 ≤ n ≤ 50000) and k (1 ≤ k ≤ 100).
• The second line contains n integers a1, a2, ..., an.
• 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 case print the answer in one line.