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 ∑_{i=1}^{n-1} ∑_{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.

Input

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

The first line of each test case contains a single integer n (2 ≤ n ≤ 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 ≤ u_i, v_i ≤ n; u_i ≠ v_i) — indices of vertices connected by the i-th edge.

Next line contains a single integer m (1 ≤ m ≤ 6 ⋅ 10^4) — the number of prime factors of k.

Next line contains m prime numbers p_1, p_2, …, p_m (2 ≤ p_i < 6 ⋅ 10^4) such that k = p_1 ⋅ p_2 ⋅ … ⋅ 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 ⋅ 10^4, and the given edges for each test cases form a tree.

Output

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

Example

Input


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


Output


17
18
286

Note

In the first test case, one of the optimal ways is on the following image:

<image>

In this case, f(1,2)=1, f(1,3)=3, f(1,4)=5, f(2,3)=2, f(2,4)=4, f(3,4)=2, so the sum of these 6 numbers is 17.

In the second test case, one of the optimal ways is on the following image:

<image>

In this case, f(1,2)=3, f(1,3)=1, f(1,4)=4, f(2,3)=2, f(2,4)=5, f(3,4)=3, so the sum of these 6 numbers is 18.
import java.lang.ref.PhantomReference;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class D {
    static Scanner sc = new Scanner(System.in);
    static ArrayList<Integer>[] G;
    static long[] k;
    static ArrayList<Long> E;
    static int n;
    static int mod = 1000000007;

    public static void main(String[] args){
        int n = sc.nextInt();
        for (int i=0;i<n;i++){
            Solve();
        }
    }
    private static void Solve(){
        n = sc.nextInt();
        G = new ArrayList[n+1];
        E = new ArrayList<>();
        for (int i=0;i<n-1;i++){
            int node1 = sc.nextInt();
            int node2 = sc.nextInt();
            add2(node1,node2);
            add2(node2,node1);
        }
        int p = sc.nextInt();
        k = new long[p];
        for (int i=0;i<p;i++){
            k[i] = sc.nextInt();
        }
        dfs(-1,1);
        Arrays.sort(k);
        Collections.sort(E);
        long ans = 0;
        long [] fac = new long[n-1];
        Arrays.fill(fac,1);
       // System.out.println(n);
       // System.out.println(p);
        //System.out.println();
        if (p<=n-1){
            for (int i=p-1,j=n-2;i>=0;i--,j--){
                fac[j] = k[i];
            }
        }else{
            for (int i=0;i<p;i++){
                int j = Math.min(i,n-2);
                fac[j] = fac[j]*k[i]%mod;
            }
        }

        for (int i=n-2;i>=0;i--){
            ans += fac[i]*E.get(i)%mod;
            ans %= mod;
        }
        System.out.println(ans);

    }

    private static void add2(int node1,int node2){
        if (G[node1]!=null){
            G[node1].add(node2);
        }else {
            G[node1] = new ArrayList();
            G[node1].add(node2);
        }
    }
    private static int dfs(int root, int node){
        int size = 1;
        for (int i=0;i<G[node].size();i++){
            if (G[node].get(i)!=root){
               int subsize = dfs(node,G[node].get(i));
                E.add((long)subsize*(long)(n-subsize));
                size += subsize;
            }
        }

        return size;
    }
}
/*
10
16
5 10
16 1
14 1
7 5
13 2
16 11
1 7
1 4
3 14
8 16
1 6
4 9
4 12
5 13
1 15
18
45893 9901 51229 15511 46559 28433 4231 30241 29837 34421 12953 6577 12143 52711 40493 89 34819 28571
*
*
* */