Counting Valid Non‐Tree Edge Selections for s-DFS Trees

Given a tree \(T=(V,E_T)\) with \(n\) vertices (vertices are numbered from \(1\) to \(n\)) and exactly \(n-1\) edges, along with \(m\) extra edges (called non‐tree edges) and exactly \(k\) designated critical vertices, we want to count the number of ways to choose a subset (possibly empty) of the non‐tree edges such that the following condition holds.

Let \(G=(V, E_T \cup E')\) be the graph obtained by taking the tree \(T\) and adding a chosen subset \(E'\) of the \(m\) non–tree edges. We say that the tree \(T\) is an s-DFS tree of \(G\) if there exists a critical vertex \(s\) (i.e. one of the designated vertices) for which a depth-first search procedure starting from \(s\) (using an appropriate search order) produces exactly \(T\) as the DFS spanning tree.

The DFS algorithm works as follows on a connected, simple (no self–loops or multiple edges) undirected graph \(G=(V,E)\):

1. Initialize an empty stack \(S\) and let \(T=(V,\emptyset)\).
2. Push the starting vertex \(s\) onto \(S\).
3. Visit the vertex \(u\) at the top of \(S\) and mark it as visited.
4. If there exists an unvisited vertex \(v\) adjacent to \(u\), arbitrarily choose one such vertex, add the edge \((u,v)\) to \(T\), push \(v\) onto \(S\) and return to step 3. If no such vertex exists, pop \(u\) from \(S\).

It can be proven that when \(G\) is connected, the algorithm returns a spanning tree of \(G\). However, the DFS tree \(T\) produced may not be unique; it depends on the order in which neighbors are visited (i.e. the choice made in step 4). For a fixed starting vertex \(s\), if there is a way to choose the search order so that the DFS procedure produces exactly \(T\), we say that \(T\) is an s-DFS tree of \(G</em>.

Your task is the following: Given the tree \(T\) with \(n\) vertices, \(m\) non–tree edges (which do not coincide with any edge of \(T\)) and exactly \(k\) critical vertices, count how many ways there are to select a subset of the non–tree edges (possibly selecting none) such that there exists some critical vertex \(s\) for which \(T\) is an \(s\)-DFS tree of \(G\).

Observation: A necessary and sufficient condition for \(T\) to be an \(s\)-DFS tree is that every non–tree edge \((u,v)\) added to \(T\) connects two vertices that are in an ancestor–descendant relation in \(T\) when the tree is rooted at \(s\). Equivalently, if we define \(d(s,x)\) as the distance from \(s\) to \(x\) in \(T\), then for any non–tree edge \((u,v)\) (assume \(d(s,u)\le d(s,v)\)), it must hold that \[ d(s,v)=d(s,u)+d_T(u,v), \] which is equivalent to \(d_T(u,v)=|d(s,v)-d(s,u)|\).

Since an extra edge that does not satisfy the above cannot be present if \(T\) is to be an \(s\)-DFS tree, when choosing a subset \(E'\) of the extra edges, for each critical vertex \(s\) the chosen edges must all be "safe" (i.e. satisfy the condition with respect to \(s\)). The answer is the number of subsets \(E'\) for which there exists at least one critical vertex \(s\) such that every chosen non–tree edge is safe with respect to \(s\).

Since the answer can be very large, output it modulo \(10^9+7\).

inputFormat

The input is given as follows:

n m k
u1 v1
... (n-1 lines for the edges of T) ...
u'_1 v'_1
... (m lines for the non–tree edges) ...
s1 s2 ... sk

</p>

Here, the tree \(T\) has vertices numbered from 1 to n and exactly n-1 edges. The next m lines describe the non–tree edges. Finally, a line with k distinct integers indicates the critical vertices.

outputFormat

Output a single integer: the number of valid ways to choose a subset of the non–tree edges, modulo \(10^9+7\).

sample

3 1 1
1 2
2 3
1 3
1

2