GTW likes tree

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$.

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.

In the output file, there should be exactly $T$ lines, each of which contains exactly one integer $ans$, which is defined above.

1
2
1 2
2 2
2
1
2

8

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++.

BestCoder Round #66 (div.1)