Problem Description

Depth-First Search (DFS) is a common search algorithm. Using this algorithm, we can start from an undirected connected graph $G = (V, E)$ without multiple edges or self-loops, and a starting point $s$, to obtain a tree $T$.

The algorithm's flow is described as follows:

1. Initialize the stack $S$ as empty and set $T = (V, \emptyset)$, meaning $T$'s edge set is initially empty.
2. Push the starting point $s$ onto $S$.
3. Visit the top node $u$ of the stack and mark $u$ as "visited".
4. If there are adjacent nodes to $u$ that have not been visited, arbitrarily select one of these nodes, denoted as $v$. Add the edge $(u, v)$ to $T$'s edge set, push $v$ onto stack $S$, and then return to step 3. If no such nodes exist, pop node $u$ from the stack.

It can be proven that when graph $G$ is connected, this algorithm will yield a spanning tree $T$ of the graph. However, the resulting tree $T$ may not be unique, depending on the order of search, specifically the vertex chosen in step 4 of the algorithm. Given a starting point $s$, if a specific search order can be chosen such that the resulting tree is exactly $T$, we call $T$ an $s$-dfs tree of $G$.

Now, given a tree $T$ with $n$ vertices, numbered from $1$ to $n$, and an additional $m$ edges. We guarantee that these $m$ edges are distinct, connect different vertices, and are distinct from the $n - 1$ tree edges in $T$. We call these additional edges non-tree edges. Among these $n$ vertices, exactly $k$ vertices are designated as key points.

You want to know how many ways there are to select these $m$ non-tree edges (you can choose none) such that: after adding the selected non-tree edges to $T$ to form graph $G$, there exists a key point $s$ such that $T$ is an $s$-dfs tree of $G$.

Since the answer may be very large, you only need to output the number of ways modulo $(10^9 + 7)$.

Input Format

The first line of input contains an integer $c$, indicating the test point number. $c = 0$ means this test point is a sample.

The second line contains three positive integers $n, m, k$, representing the number of vertices, the number of non-tree edges, and the number of key points, respectively.

The next $n - 1$ lines each contain two positive integers $u, v$, representing an edge in tree $T$. It is guaranteed that these $n - 1$ edges form a tree.

The next $m$ lines each contain two positive integers $a, b$, representing a non-tree edge. It is guaranteed that $(a, b)$ does not overlap with the tree edges and there are no duplicate edges.

The last line contains $k$ positive integers $s_1, s_2, \dots, s_k$, representing the numbers of the $k$ key points. It is guaranteed that $s_1, s_2, \dots, s_k$ are distinct.

Output Format

Output a single line containing a non-negative integer, representing the number of ways modulo $(10^9 + 7)$.

Sample Input and Output

Sample Input #1

0
4 2 2
1 2
2 3
3 4
1 3
2 4
2 3

Sample Output #1

3

Sample Input #2

See attached file dfs/dfs2.in.

Sample Output #2

See attached file dfs/dfs2.ans.

Sample Input #3

See attached file dfs/dfs3.in.

Sample Output #3

See attached file dfs/dfs3.ans.

Sample Input #4

See attached file dfs/dfs4.in.

Sample Output #4

See attached file dfs/dfs4.ans.

Sample Input #5

See attached file dfs/dfs5.in.

Sample Output #5

See attached file dfs/dfs5.ans.

Sample Input #6

See attached file dfs/dfs6.in.

Sample Output #6

See attached file dfs/dfs6.ans.

Notes/Hints

[Sample Explanation #1]

In this example, there are three ways to select the non-tree edges: select only edge $(1, 3)$, select only edge $(2, 4)$, or select none of the non-tree edges.

If only edge $(1, 3)$ is selected, or if no non-tree edges are selected, we find that $T$ is both a $3$-dfs tree of graph $G$. The specified search order is as follows:

1. Push $3$ onto stack $S$. Now $S = [3]$.
2. Mark $3$ as "visited".
3. Since $3$ is connected to $2$ and $2$ is "unvisited", push $2$ onto $S$ and add $(3, 2)$ to tree $T$. Now $S = [3, 2]$.
4. Mark $2$ as "visited".
5. Since $2$ is connected to $1$ and $1$ is "unvisited", push $1$ onto $S$ and add $(2, 1)$ to tree $T$. Now $S = [3, 2, 1]$.
6. Since all adjacent points to $1$ are "visited", pop $1$ from the stack. Now $S = [3, 2]$.
7. Since all adjacent points to $2$ are "visited", pop $2$ from the stack. Now $S = [3]$.
8. Since $3$ is connected to $4$ and $4$ is "unvisited", push $4$ onto $S$ and add $(3, 4)$ to tree $T$. Now $S = [3, 4]$.
9. Since all adjacent points to $4$ are "visited", pop $4$ from the stack. Now $S = [3]$.
10. Since all adjacent points to $3$ are "visited", pop $3$ from the stack. Now $S$ is empty again.

If only edge $(2, 4)$ is selected, we can show that $T$ is a $2$-dfs tree of graph $G$. The specified search order is as follows:

1. Push $2$ onto stack $S$. Now $S = [2]$.
2. Mark $2$ as "visited".
3. Since $2$ is connected to $3$ and $3$ is "unvisited", push $3$ onto $S$ and add $(2, 3)$ to tree $T$. Now $S = [2, 3]$.
4. Mark $3$ as "visited".
5. Since $3$ is connected to $4$ and $4$ is "unvisited", push $4$ onto $S$ and add $(3, 4)$ to tree $T$. Now $S = [2, 3, 4]$.
6. Since all adjacent points to $4$ are "visited", pop $4$ from the stack. Now $S = [2, 3]$.
7. Since all adjacent points to $3$ are "visited", pop $3$ from the stack. Now $S = [2]$.
8. Since $2$ is connected to $1$ and $1$ is "unvisited", push $1$ onto $S$ and add $(2, 1)$ to tree $T$. Now $S = [2, 1]$.
9. Since all adjacent points to $1$ are "visited", pop $1$ from the stack. Now $S = [2]$.
10. Since all adjacent points to $2$ are "visited", pop $2$ from the stack. Now $S$ is empty again.

[Sample Explanation #2]

This sample satisfies the constraints of test points $4 \sim 6$.

[Sample Explanation #3]

This sample satisfies the constraints of test points $10 \sim 11$.

[Sample Explanation #4]

This sample satisfies the constraints of test points $12 \sim 13$.

[Sample Explanation #5]

This sample satisfies the constraints of test points $14 \sim 16$.

[Sample Explanation #6]

This sample satisfies the constraints of test points $23 \sim 24$.

[Data Range]

For all test data, it is guaranteed that $1 \le k \le n \le 5 \times 10^5$ and $1 \le m \le 5 \times 10^5$.

Special Property A: In $T$, vertex $i$ is connected to vertex $i + 1$ ($1 \le i < n$).

Special Property B: If all $m$ non-tree edges are added to $T$ to form a graph $G$, then $T$ is a $1$-dfs tree of $G$.

Note that vertex $1$ is not necessarily one of the $k$ key points.

见题面 Input 部分

见题面 Output 部分