Mr. Bread has a tree TT with nn vertices, labeled by 1,2,…,n1,2,…,n. Each vertex of the tree has a positive integer value wiwi.
The value of a non-empty tree TT is equal to w1×w2×⋯×wnw1×w2×⋯×wn. A subtree of TT is a connected subgraph of TT that is also a tree.
Please write a program to calculate the number of non-empty subtrees of TT whose values are not larger than a given number mm.
Input
The first line of the input contains an integer T(1≤T≤10)T(1≤T≤10), denoting the number of test cases.
In each test case, there are two integers n,m(1≤n≤2000,1≤m≤106)n,m(1≤n≤2000,1≤m≤106) in the first line, denoting the number of vertices and the upper bound.
In the second line, there are nn integers w1,w2,…,wn(1≤wi≤m)w1,w2,…,wn(1≤wi≤m), denoting the value of each vertex.
Each of the following n−1n−1 lines contains two integers ui,vi(1≤ui,vi≤n,ui≠vi)ui,vi(1≤ui,vi≤n,ui≠vi), denoting an bidirectional edge between vertices uiui and vivi.
Output
For each test case, print a single line containing an integer, denoting the number of valid non-empty subtrees. As the answer can be very large, output it modulo 109+7109+7.