Depth-first search (DFS) is a common search algorithm. Using this algorithm, we can obtain a tree $T$ from an undirected connected graph $G = (V, E)$ with no multiple edges or self-loops, starting from a given vertex $s$.

The algorithm proceeds as follows: 1. Initialize an empty stack $S$ and set $T = (V, \emptyset)$, meaning the edge set of $T$ is initially empty. 2. Push the starting vertex $s$ onto $S$. 3. Visit the vertex $u$ at the top of the stack and mark $u$ as "visited". 4. If there exists a vertex $v$ adjacent to $u$ that has not been visited, choose one such vertex $v$ arbitrarily. Add the edge $(u, v)$ to the edge set of $T$, push $v$ onto the stack $S$, and return to step 3. If no such vertex exists, pop the vertex $u$ from the stack.

It can be proven that when $G$ is a connected graph, this algorithm will produce a spanning tree $T$ of $G$. However, the tree $T$ obtained by the algorithm may not be unique; it depends on the search order, which is the sequence of vertices chosen in step 4. Given a starting vertex $s$, if there exists a specific search order such that the tree produced by the algorithm is exactly $T$, we call $T$ an $s$-dfs tree of $G$.

You are given a tree $T$ with $n$ vertices, labeled $1 \sim 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 $m$ edges "non-tree edges". Among these $n$ vertices, we have designated exactly $k$ vertices as "key vertices".

You want to know how many ways there are to choose a subset of these $m$ non-tree edges (you may choose none) such that, after forming a graph $G$ using the edges of $T$ and the chosen non-tree edges, there exists some key vertex $s$ such that $T$ is an $s$-dfs tree of $G$.

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

Input

The first line contains an integer $c$, representing the test case number. $c = 0$ indicates that this test case 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 vertices, 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 coincide with any tree edge and there are no multiple edges. The last line contains $k$ positive integers $s_1, s_2, \dots, s_k$, representing the labels of the $k$ key vertices. It is guaranteed that $s_1, s_2, \dots, s_k$ are distinct.

Output

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

Examples

Input 1

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

Output 1

3

Constraints

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

Special Property A: It is guaranteed that in $T$, vertex $i$ is connected to vertex $i+1$ ($1 \le i < n$). Special Property B: It is guaranteed that if we form a graph $G$ using the edges of $T$ and all $m$ non-tree edges, then $T$ is a $1$-dfs tree of $G$.

Please note that vertex $1$ is not necessarily one of the $k$ key vertices.