L. As crychic wanes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As her wallet became thinner day by day, Saki realized — those days in crychic would never come back. Carrying the Maybach she bought for 96 yuan on her shoulders, she once again rushed along the muddy roads.

The road system of Saki's city can be seen as a tree with $$$n$$$ nodes, rooted at node $$$1$$$. Initially, each node $$$u$$$ has a wage multiplier $$$a_u$$$. Because of the war, the passenger flow at some nodes (at most $$$100$$$ nodes) is very unstable. These nodes are called special nodes. In the next $$$q$$$ days, on day $$$i$$$, the wage multipliers of all special nodes will be changed to $$$p_i$$$.

Let the set of nodes Saki passes during one trip be $$$T$$$. Then the wage of that day is $$$\displaystyle \prod_{u \in T} a_u$$$. To keep service quality, Saki follows these rules when making a trip:

  • She starts from node $$$1$$$.

  • She only moves along edges of the tree to adjacent nodes, but she may pass the same node more than once.

  • If she passes node $$$u$$$ during a trip, then in this trip she either passes none of the children of $$$u$$$, or passes all children of $$$u$$$.

Two trip plans are different if and only if the sets of nodes they pass are different.

For day $$$i$$$, Saki asks you to calculate the sum of wages of all valid trip plans on that day.

As the answer may be very large, you only need to output it modulo $$$10^9+7$$$.

Input

Each test file contains multiple test cases. The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, the number of test cases.

For each test case, the first line contains two integers $$$n,q$$$ $$$(1 \leq n,q \leq 2 \times 10^5)$$$, the number of nodes and the number of days.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(0 \leq a_i \leq 10^6)$$$, representing the initial wage multiplier of each node. Among them, the nodes with initial multiplier $$$0$$$ are special nodes, and the number of special nodes in each test case does not exceed $$$100$$$.

The next $$$n-1$$$ lines each contain two integers $$$u_i,v_i$$$ $$$(1 \leq u_i,v_i \leq n)$$$, meaning there is an edge connecting nodes $$$u_i$$$ and $$$v_i$$$.

The next $$$q$$$ lines each contain one integer $$$p_i$$$ $$$(1 \leq p_i \leq 10^9)$$$. Its meaning is described in the statement.

It is guaranteed that the sums of $$$n,q$$$ over all test cases do not exceed $$$2 \times 10^5$$$.

Output

For each test case, output $$$q$$$ lines, each containing one integer, the sum of wages of all valid trip plans on that day modulo $$$10^9+7$$$.

Example
Input
1
4 3
2 0 2 2
2 3
3 4
2 1
3
2
4
Output
44
30
58
Note

In Sample 1, the road structure, the special nodes, and the wage multipliers on each day are as follows:

On the first day, the valid trip plans and their wages are:

Trip planWage
$$$[1]$$$$$$2$$$
$$$[1,2]$$$$$$2\times3=6$$$
$$$[1,2,3]$$$$$$2\times 3\times 2=12$$$
$$$[1,2,3,4]$$$$$$2\times 3\times 2\times 2=24$$$

The sum of wages of all plans is $$$2+6+12+24=44$$$.