Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

You are given a tree of $N$ nodes rooted at node $1$. Each node $u$ initially has a positive value $a_{u}$ associated with it.

You randomly choose one node in the tree and change its value to zero. If any node $u$ has a value equal to $0$, a random node $v$ will be chosen in the subtree of $u$ ($u \neq v$), and the values $a_{u}$ and $a_{v}$ will be swapped, hence the value of the node $v$ will become zero and the process will continue until the zero is on a leaf node. At this point, we will call the tree a final tree.

Note: there is exactly one node with a value equal to zero in a final tree and that node is a leaf node.

Your task is to tell how many different final trees are possible. Two final trees are different if there exists at least one node $u$, such that the value of the node $u$ in one final tree differs from the value of the node $u$ in the other final tree. Since the answer can be large, print it modulo $10^{9} +7$.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow.
The first line of each test case contains an integer $N$, the number of nodes.
Each of the next $N-1$ lines contains two integers $u$ and $v$, denoting that there is an undirected edge between the node $u$ and the node $v$.
The next line contains $N$ integers $a_{1},\ldots, a_{N}$.

------ Output ------
For each test case, output on a new line, number of different final trees possible, modulo $10^{9}+7$.

------ Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ u, v ≤ N$
$1≤ a_{i}≤ 10^{9}$
The edges form a tree structure.
The sum of $N$ over all test cases does not exceed $10^{6}$.

------ Sample Input ------

3
1
1
4
1 2
2 3
2 4
1 1 1 2
7
1 2
1 3
2 4
2 5
3 6
3 7
1 2 3 4 1 2 1

------ Sample Output ------

1
4
14

------ Explanation ------
For the first test case, the only possible final tree is when node $1$ is chosen and its value becomes 0.
For the second test case, the four possible final trees are:
- [ 1, 1, 1, 0 ]
- [ 1, 1, 0, 2 ]
- [ 1, 2, 1, 0 ]
- [ 2, 1, 1, 0 ]

( The $i$-th number in the array denotes the value of node $i$ in the final tree).

见题面

见题面