A Game with Two Trees

Albert is playing a game with two trees. The first tree $T_A$ has $N_A$ nodes, written $a_1, a_2, \dots, a_{N_A}$. The nodes in $S_A$ are called "special". The second tree $T_B$ has $N_B$ nodes, written $b_1, b_2, \dots, b_{N_B}$. The nodes in $S_B$ are special.

The figure below shows an example where both trees have 3 nodes ($N_A = N_B = 3$). $S_A$ has 3 nodes and $S_B$ has 1 node. Special nodes are drawn with double lines.

Pick one node from each tree and connect them with an edge. Let $U_{i,j}$ be the tree formed by adding the edge $e = (a_i, b_j)$ to $T_A \cup T_B$. The score $S(i, j)$ of $U_{i,j}$ is the number of simple paths in $U_{i,j}$ that contain exactly one node from $S_A$ and exactly one node from $S_B$. Call such a path a "perfect path".

In the example, $S(1, 1) = 1$, $S(1, 2) = 3$, and $S(1, 3) = 1$. For $U_{1,1}$, the only perfect path is $a_1 - b_1 - b_3 - b_2$. For $U_{1,2}$, there are three perfect paths: $a_1 - b_2$, $a_1 - b_2 - b_3$, and $a_1 - b_2 - b_3 - b_1$. For $U_{1,3}$, the only perfect path is $a_1 - b_3 - b_2$.

The values $S(2, 1) = 1$, $S(2, 2) = 3$, $S(2, 3) = 1$, $S(3, 1) = 1$, $S(3, 2) = 3$, and $S(3, 3) = 1$ are obtained the same way.

Computing $S(i, j)$ for one pair is easy, so Albert wants to compute $V(T_A, T_B) = \sum_{1 \le i \le N_A} \sum_{1 \le j \le N_B} S(i, j) \cdot (i + j)$. In the example, this value is 60.

Given both trees, compute $V(T_A, T_B)$.

The first line contains the number of test cases $C$.

The first line of each test case contains $N_A$ and $M_A = |S_A|$, separated by a space. The second line contains the $M_A$ indices of the nodes in $S_A$, separated by spaces. The next $N_A - 1$ lines each contain two integers, separated by a space, describing an edge of $T_A$.

Then comes a line with $N_B$ and $M_B = |S_B|$, separated by a space. The next line contains the $M_B$ indices of the nodes in $S_B$, separated by spaces. The last $N_B - 1$ lines each contain two integers describing an edge of $T_B$.

For each test case, print $V(T_A, T_B)$ modulo $10^9 + 7$ on its own line.

• $1 \le C \le 10$
• $2 \le N_A, N_B \le 65,000$
• $1 \le M_A \le N_A$
• $1 \le M_B \le N_B$
• No element appears twice in $S_A$.
• No element appears twice in $S_B$.
• Both $T_A$ and $T_B$ are valid trees.