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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Solution1401D {
  public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    Solver1401D solver = new Solver1401D();
    int n = in.nextInt();
    for (int i = 0; i < n; i++) {
      solver.solve(i, in, out);
    }
    out.close();
  }

  static class Solver1401D {
    public static final long MOD = 1000000007L;
    public void solve(int testNumber, InputReader in, PrintWriter out) {
      //System.out.println("start");
      int n = in.nextInt();
      Map<Integer, Set<Integer>> ns = new HashMap<>();
      boolean[] v = new boolean[n+1];
      int[] cs = new int[n+1];
      int[][] edges = new int[n-1][2];
      int[] ps = new int[n+1];
      for (int i = 0; i < n - 1; i++) {
        int a = in.nextInt(), b = in.nextInt();
        edges[i][0] = a;
        edges[i][1] = b;
        addEdge(ns, a, b);
        addEdge(ns, b, a);
      }

      int m = in.nextInt();
      int[] p = new int[m];
      for (int i = 0; i < m; i++) {
        p[i] = in.nextInt();
      }
      Arrays.sort(p);

      getC(1, cs, v, ns, ps);
      long result = 0L;
      long[] w = new long[n-1];
      for (int i = 0; i < n - 1; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int tmp = 0;
        if (ps[a] == b) {
          tmp = cs[a];
        } else {
          tmp = cs[b];
        }
        w[i] = (long)tmp * (long)(n - tmp);
        //System.out.println("w : " + w[i]);
      }
      Arrays.sort(w);
      int i = m - 1;
      if (m <= w.length) {
        for (int j = w.length - 1; j >= 0; j--) {
          long wv = w[j];
          if (i >= 0) {
            //System.out.println("wv : " + wv + " " + p[i]);
            result += wv * (long) (p[i]);
            i--;
          } else {
            //System.out.println("wv : " + wv);
            result += wv;
          }
          result = result % MOD;
        }
      } else {
        long p0 = 1L;
        for (int j = 0; j < m - w.length + 1; j++) {
          p0 *= p[i];
          p0 = p0 % MOD;
          i--;
        }
        for (int j = w.length - 1; j >= 0; j--) {
          long wv = w[j];
          if (j == w.length - 1) {
            //System.out.println("wv : " + wv + " " + p0);
            result += wv * p0;
          } else {
            //System.out.println("wv : " + wv + " " + p[i]);
            result += wv * (long) (p[i]);
            i--;
          }
          result = result % MOD;
        }
      }
      out.println(result);
    }

    private int getC(int node, int[] cs, boolean[] v, Map<Integer, Set<Integer>> ns, int[] ps) {
      v[node] = true;
      Set<Integer> nextns = ns.get(node);
      int res = 1;
      if (nextns != null) {
        for (Integer nextn : nextns) {
          if (!v[nextn]) {
            res += getC(nextn, cs, v, ns, ps);
          } else {
            ps[node] = nextn;
          }
        }
      }
      cs[node] = res;
      //System.out.println(node + " " + cs[node]);
      return res;
    }

    private void addEdge(Map<Integer, Set<Integer>> ns, int a, int b) {
      Set<Integer> list = ns.get(a);
      if (list == null) {
        list = new HashSet<>();
        ns.put(a, list);
      }
      list.add(b);
    }
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}