두 개의 트리를 이용하는 놀이

문제

Albert는 2개의 트리 (tree) 를 이용한 놀이를 하고 있다. 첫 번째 트리는 $T_A$ 인데 $N_A$ 개의 노드를 갖고 있으며 ($a_1, a_2, \dots, a_{N_A}$ 로 나타낸다) 그 중 $S_A$ 에 속한 노드는 "특별한" 노드로 여겨진다. 마찬가지로 두 번째 트리는 $T_B$ 인데 $N_B$ 개의 노드를 갖고 있으며 ($b_1, b_2, \dots, b_{N_B}$ 로 나타낸다) 그 중 $S_B$ 에 속한 노드는 "특별한" 노드로 여겨진다. 아래 그림은 두 트리가 각각 3개의 노드를 가진 예제인데 (즉, $N_A = N_B = 3$), $S_A$ 에는 3개의 노드가 있고 $S_B$ 에는 1개의 노드가 있다. 특별한 노드는 그림에서 2중선으로 표시되어있다.

각 트리에서 노드를 하나씩 선택하여 간선으로 연결하면 하나의 트리로 합칠 수 있는데, 간선 $e = (a_i, b_j)$ 를 $T_A \cup T_B$ 에 추가한 트리를 $U_{i, j}$ 라 했을 때, $U_{i, j}$ 의 "완벽도" $S(i, j)$ 는 아래 규칙에 따라 정한다:

트리 $U_{i, j}$ 에 존재하는 모든 단순 경로 (simple path) 중 $S_A$ 에 속한 노드를 정확히 하나 포함하고 $S_B$ 에 속한 노드를 정확히 하나 포함하는 경로의 개수. 이러한 경로를 "완벽한 경로"라 하자.

위 예제의 경우 $S(1, 1) = 1, S(1, 2) = 3, S(1, 3) = 1$ 임을 아래 그림을 통해 확인할 수 있다.

가장 위의 그림: 좌측의 트리는 $a_1$ 과 $b_1$을 연결하여 얻게되는 $U_{1, 1}$ 를 보여주며, 이 때 완벽한 경로는 $a_1 - b_1 - b_3 - b_2$ 로 유일하다. 따라서 $S(1, 1) = 1$ 이다.
중앙의 그림: 좌측의 트리는 $a_1$ 과 $b_2$을 연결하여 얻게되는 $U_{1, 2}$ 를 보여주며, 이 때 완벽한 경로는 총 3개 있으므로 $S(1, 2) = 3$ 이다: $a_1 - b_2$, $a_1 - b_2 - b_3$, 그리고 $a_1 - b_2 - b_3 - b_1$.
가장 아래 그림: 좌측의 트리는 $a_1$ 과 $b_3$을 연결하여 얻게되는 $U_{1, 3}$ 를 보여주며, 이 때 완벽한 경로는 $a_1 - b_3 - b_2$ 로 유일하다. 따라서 $S(1, 3) = 1$ 이다.

비슷한 방법으로 $S(2, 1) = 1, S(2, 2) = 3, S(2, 3) = 1, S(3, 1) = 1, S(3, 2) = 3, S(3, 3) = 1$ 임을 보일 수 있다.

임의의 $i, j$에 대하여 $S(i, j)$ 를 구하는 것은 너무 쉽기 때문에, Albert는 다음 값을 구해보기로 했다: $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)$. 위 예제의 경우 이 값은 60 이다.

입력으로 두 트리에 대한 정보가 주어졌을 때, $V(T_A, T_B)$ 값을 구해보자.

입력

입력 첫 줄에 테스트 케이스의 수 $C$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N_A$ 와 $M_A = |S_A|$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 $M_A$ 개의 정수가 공백으로 구분되어 주어지는데, 이는 $S_A$ 에 속한 노드의 인덱스를 나타낸다. 다음 $N_A - 1$ 줄에 걸쳐 $T_A$ 의 간선이 주어지는데 각 줄에 간선 하나를 표현하는 두개의 정수가 공백으로 구분되어 주어진다. 이어서 두 번째 트리를 묘사하는 $N_B$ 와 $M_B = |S_B|$ 가 공백으로 구분되어 주어진다. 다음 줄에는 $M_B$ 개의 정수가 공백으로 구분되어 주어지는데, 이는 $S_B$ 에 속한 노드의 인덱스를 나타낸다. 다음 $N_B - 1$ 줄에 걸쳐 $T_B$ 의 간선이 주어지는데 각 줄에 간선 하나를 표현하는 두개의 정수가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스의 정답인 $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)$ 를 출력한다. 단, 이 값이 매우 클 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 출력한다.

제한

$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$
입력으로 주어지는 $S_A$ 에 중복된 원소는 없다.
입력으로 주어지는 $S_B$ 에 중복된 원소는 없다.
입력으로 주어지는 두 트리 $T_A, T_B$ 가 올바르지 않은 트리인 경우는 없다.