You are given a tree that consists of $n$ nodes. You should label each of its $n-1$ edges with an integer in such way that satisfies the following conditions:

• each integer must be greater than $0$;
• the product of all $n-1$ numbers should be equal to $k$;
• the number of $1$-s among all $n-1$ integers must be minimum possible.

Let's define $f(u,v)$ as the sum of the numbers on the simple path from node $u$ to node $v$. Also, let $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$ be a distribution index of the tree.

Find the maximum possible distribution index you can get. Since answer can be too large, print it modulo $10^9 + 7$.

In this problem, since the number $k$ can be large, the result of the prime factorization of $k$ is given instead.

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines describes an edge: the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$) — indices of vertices connected by the $i$-th edge.

Next line contains a single integer $m$ ($1 \le m \le 6 \cdot 10^4$) — the number of prime factors of $k$.

Next line contains $m$ prime numbers $p_1, p_2, \ldots, p_m$ ($2 \le p_i < 6 \cdot 10^4$) such that $k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$, the sum of $m$ over all test cases doesn't exceed $6 \cdot 10^4$, and the given edges for each test cases form a tree.

Print the maximum distribution index you can get. Since answer can be too large, print it modulo $10^9+7$.