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 javafx.util.Pair;

import java.io.*;
import java.util.*;


public class Codeforces {


    static Map<Integer,List<Integer>> edMap;
    static Map<Long,Long> dp;
    static List<Pair<Integer,Integer>> edList;
    static final int MOD = 1000000000 + 7;
    static final long KEY = 1000000;
    static int n;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();

        while (t-- > 0) {
            boolean test = false;
            n = sc.nextInt();
            edMap = new HashMap<>();
            edList = new ArrayList<>();
            for (int i=0;i<n-1;i++) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                if (t == 0 && i == 0 && l == 69702 && r == 32259) {
                    test = true;
                }
                edList.add(new Pair<>(l,r));
                putValue(l,r);
                putValue(r,l);
            }
            int m = sc.nextInt();
            dp = new HashMap<>(m);
            List<Long> values = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                long tmp = sc.nextLong();
                values.add(tmp);
            }

            shuffle(values);
            values.sort(Comparator.reverseOrder());
            if (m > n-1) {
                long tmp = values.get(0);
                for (int i = 1; i <= m-n+1; i++) {
                    tmp = (tmp*(long)values.get(i))%MOD;
                }
                List<Long> tmplist = new ArrayList<>();
                tmplist.add(tmp);
                tmplist.addAll(values.subList(m - n + 2, m));
                values = tmplist;
            } else {
                for (int i = 0; i < n-1-m; i++) {
                    values.add(1L);
                }
                //values.sort(Comparator.reverseOrder());
            }

            //if(test) System.out.println("cal values done");

            List<Long> nums = new ArrayList<>();
            dfs(1,0,new int[n+1],nums);
//            int ik = 0;
//            for (Pair<Integer, Integer> edNode : edList) {
//                ik++;
//                if (ik == n/10000 && test) System.out.println("cal 1/10000 dp done");
//                if (ik == n/1000 && test) System.out.println("cal 1/1000 dp done");
//                if (ik == n/100 && test) System.out.println("cal 1/100 dp done");
//                if (ik == n/2 && test) System.out.println("cal half dp done");
//                int l = edNode.getKey();
//                int r = edNode.getValue();
//                long lnum = work(l,r);
//                long rnum = work(r,l);
//                long num = lnum;
//                num = (num*rnum);
//                nums.add(num);
//            }
            //if(test) System.out.println("cal dp done");
            shuffle(nums);
            nums.sort(Comparator.reverseOrder());
            //if(test) System.out.println("cal sort nums done");
            for (int i = 0; i < nums.size(); i++) {
                nums.set(i,nums.get(i)%MOD);
            }
            long ans = 0;
            for (int i = 0; i < nums.size(); i++) {
                ans = (ans+((long)nums.get(i))*values.get(i) + MOD)%MOD;
            }
            System.out.println(ans);
        }

    }

    private static int dfs(int now ,int fa,int[] flag,List<Long> nums) {
        List<Integer> list = edMap.get(now);
        flag[now] = 1;
        for (Integer ed : list) {
            if (ed != fa) {
                flag[now]+=dfs(ed,now,flag,nums);
            }
        }
        if (fa != 0) nums.add(flag[now]*(long)(n-flag[now]));
        return flag[now];

    }

    private static long work(int l, int r) {
        Long ans = dp.get(l+(long)(r*KEY));
        if (ans != null) {
            return ans;
        }
        List<Integer> list = edMap.get(r);
        long sum = 1;
        for (Integer node : list) {
            if (node != l) {
                sum = (sum+work(r,node))%MOD;
            }
        }
        dp.put(l+(long)(r*KEY),sum);
        return sum;
    }

    private static void putValue(int l, int r) {
        List<Integer> list = edMap.getOrDefault(l, new ArrayList<>());
        list.add(r);
        edMap.put(l,list);

    }

    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    static void shuffle(long[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            long temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    static void shuffle(List<Long> a) {
        Random get = new Random();
        for (int i = 0; i < a.size(); i++) {
            int r = get.nextInt(a.size());
            long temp = a.get(i);
            a.set(i,a.get(r));
            a.set(r,temp);
        }
    }


}
