Counting on Tree
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^9 + 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
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 case print the answer in one line.