GTW has a tree of $n$ nodes, in which $m$ nodes are special nodes. The value of node $i$ is $v_i$.
$Dis(x, y)$ is defined as the greatest common divisor of the nodes in the chain between node $x$ and node $y$.
$Jabby(x, y)$ is defined as the number of special nodes in the chain between node $x$ and node $y$.
You are asked to calculate the value of $ans$, which is defined as follow.
$ans=\prod_{i=1}^{n}\prod_{j=i}^{n}max(1,Dis(i,j)*min(1,jabby(i,j)))$
Because $ans$ could be very large, you only need to print $ans$ modulo $10 ^ 9 + 7$.
Input
The first line of the input file contains an integer $T$, indicating the number of test cases. ($T\leq 6$)
For each test case, there are $n + m + 2$ lines in the input file.
The first line of each test case contains a number $n$ which indicates the number of the nodes of GTW¡¯s tree. ($1\leq n\leq 200000$)
In each line of the following $n - 1$ lines, there are two numbers $x$ and $y$ which indicate that there is an undirected line between node $x$ and node $y$.
The next line contains $n$ integers, $v_1,v_2,...,v_n$, in which $v_i$ indicates the value of node $i$. ($1\leq v_i\leq100000$)
The next line contains a number $m$ which indicates the number of special nodes.
Then in each line of the following $m$ lines, there are an integer $g$ which indicates that node $g$ is a special node.
The data guarantees that the $m$ given nodes differ from each other.
Output
In the output file, there should be exactly $T$ lines, each of which contains exactly one integer $ans$, which is defined above.
Sample Input
1
2
1 2
2 2
2
1
2
Sample Output
8
Hint
In the sample above, $ans = 2\times 2\times 2 = 8$.
If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
