깊이 우선 탐색

깊이 우선 탐색은 널리 쓰이는 탐색 알고리즘이다. 이 알고리즘으로 자기 루프와 중복 간선이 없는 무방향 연결 그래프 $G = (V,E)$와 시작점 $s$에서 트리 $T$를 얻을 수 있다.

알고리즘은 다음과 같이 동작한다.

• 스택 $S$를 비우고, $T = (V, \emptyset)$로 둔다. 즉 $T$의 간선 집합은 처음에 비어 있다.
• 시작점 $s$를 $S$에 넣는다.
• 스택의 맨 위 정점 $u$를 확인하고, $u$를 방문함으로 표시한다.
• $u$와 인접하면서 아직 방문하지 않은 정점 $v$가 있으면, 그중 하나를 임의로 골라 $(u, v)$를 $T$의 간선 집합에 추가한다. 그다음 $v$를 $S$에 넣고 3번 단계로 돌아간다. 그런 정점이 없으면 $u$를 스택에서 뺀다.

$G$가 연결 그래프이면 이 알고리즘은 $G$의 신장 트리 $T$를 하나 얻는다. 다만 4번 단계에서 어느 정점을 고르느냐, 즉 탐색 순서에 따라 얻는 트리는 하나로 정해지지 않는다. 알고리즘이 얻는 트리가 정확히 $T$가 되도록 하는 탐색 순서가 존재하면, $T$를 시작점 $s$에 대한 $s$-DFS 트리라고 부른다.

$n$개의 정점에 $1$부터 $n$까지 번호가 붙은 트리 $T$와 추가 간선 $m$개가 주어진다. 이 $m$개의 간선은 서로 다르고, 양 끝점이 서로 다른 정점이며, $T$의 $n-1$개 트리 간선과도 다르다고 보장된다. 이 추가 간선을 비트리 간선이라고 부른다. $n$개의 정점 중 정확히 $k$개를 특수 정점으로 지정한다.

비트리 간선의 부분집합을 고르는 방법의 수를 구한다. 고른 비트리 간선을 $T$의 트리 간선과 합쳐 그래프 $G$를 만들었을 때, $T$가 $s$-DFS 트리가 되도록 하는 특수 정점 $s$가 존재해야 한다. 비트리 간선을 하나도 고르지 않아도 된다.

답이 매우 클 수 있으므로 $(10^9+7)$로 나눈 나머지를 출력한다.

입력의 첫 줄에 테스트 케이스 번호 $c$가 주어진다. $c = 0$이면 이 테스트 케이스는 예제 테스트이다.

둘째 줄에 정점 수 $n$, 비트리 간선 수 $m$, 특수 정점 수 $k$가 양의 정수로 주어진다.

이어서 $n-1$개의 줄에 트리 $T$의 간선 $u, v$가 한 줄에 하나씩 주어진다. 이 간선들이 트리를 이룬다고 보장된다.

이어서 $m$개의 줄에 비트리 간선 $a, b$가 한 줄에 하나씩 주어진다. $(a, b)$는 트리 간선과 겹치지 않으며, 중복된 간선도 없다고 보장된다.

마지막 줄에는 특수 정점의 번호 $s_1, s_2, ..., s_k$가 주어진다. 이 번호들은 서로 다르다.

답을 한 줄에 출력한다. 답은 $(10^9+7)$로 나눈 나머지이다.

모든 테스트 데이터에 대해 $1 \leq k \leq n \leq 5\cdot 10^5$, $1 \leq m \leq 5\cdot 10^5$이 보장된다.