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.*;
import java.util.*;
import java.math.*;

public class D {
    static final boolean RUN_TIMING = false;
    static char[] inputBuffer = new char[1 << 20];
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    final int MOD = (int)(1e9 + 7);
    int n;

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1 << 20);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        int zzz = ipar();
        for (int zz = 0; zz < zzz; zz++) {
            n = ipar();
            Vertex[] vertices = new Vertex[n];
            for (int i = 0; i < n; i++) {
                vertices[i] = new Vertex();
            }
            for (int i = 0; i < n-1; i++) {
                Vertex u = vertices[ipar()-1];
                Vertex v = vertices[ipar()-1];
                u.others.add(v);
                v.others.add(u);
            }
            int m = ipar();
            long[] factors = lapar(m);
            for (int i = 0; i < m; i++) {
                int j = (int)(Math.random() * (m-i));
                long temp = factors[i];
                factors[i] = factors[j];
                factors[j] = temp;
            }
            Arrays.sort(factors);
            if (m > n-1) {
                long[] newFactors = new long[n-1];
                for (int i = 0; i < n-1; i++) {
                    newFactors[i] = factors[i];
                }
                for (int i = n-1; i < m; i++) {
                    newFactors[n-2] *= factors[i];
                    newFactors[n-2] %= MOD;
                }
                factors = newFactors;
                m = n-1;
            }
            ArrayList<long[]> splits = new ArrayList<>();
            dfs(vertices[0], null, splits);
            Collections.sort(splits, (a, b) -> -Long.compare(a[0]*a[1], b[0]*b[1]));
            // for (long[] a : splits) {
            //     out.println(Arrays.toString(a));
            // }
            // out.println(Arrays.toString(factors));
            long ans = 0;
            for (int i = 0; i < m; i++) {
                ans += splits.get(i)[0] * splits.get(i)[1] % MOD * factors[m-i-1] % MOD;
                ans %= MOD;
                // out.println(splits.get(i)[0] * splits.get(i)[1] % MOD * factors[m-i-1] % MOD);
            }
            for (int i = m; i < n-1; i++) {
                ans += splits.get(i)[0] * splits.get(i)[1] % MOD;
                ans %= MOD;
            }
            out.println(ans);
        }
    }

    public int dfs(Vertex curr, Vertex prev, ArrayList<long[]> splits) {
        int total = 0;
        for (Vertex other : curr.others) {
            if (other == prev) {
                continue;
            }
            int under = dfs(other, curr, splits);
            splits.add(new long[] {under, n - under});
            total += under;
        }
        return total+1;
    }

    private class Vertex {
        ArrayList<Vertex> others = new ArrayList<>();
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        int len = 0;
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            inputBuffer[len] = (char)c;
            len++;
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return new String(inputBuffer, 0, len);
    }

    public String linepar() throws IOException {
        int len = 0;
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            inputBuffer[len] = (char)c;
            len++;
        }
        return new String(inputBuffer, 0, len);
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new D().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time / 1000000.0);
        }
        out.flush();
        in.close();
    }
}
