Counting Distinct DFS Trees in a Tree’s Edge‐Traversal

Consider a tree \(T\) with \(n\) nodes and \(n-1\) edges. Initially all edges are unmarked. An edge‐based DFS-like traversal is defined as follows:

1. Select an edge \(b\) as the starting (root) edge and mark it.
2. Let the current edge be \(e\). If there exists any edge \(f\) adjacent to \(e\) (two edges are adjacent if they share a common vertex) that is unmarked, choose one arbitrarily, mark it and treat it as the new current edge; then repeat step 2.
3. If no unmarked edge adjacent to \(e\) exists and \(e = b\) then the traversal ends; otherwise, backtrack: set \(e\) to the edge visited immediately before \(e\) and repeat step 2.

During this process, whenever an edge \(f\) is visited from an adjacent edge \(e\) in step 2, we build a new tree by regarding each original edge as a node and connecting the corresponding nodes \(e\) and \(f\) with a new edge. In the end, the new tree has \(n-1\) nodes and \(n-2\) edges.

Now, suppose that among the \(n-1\) edges of \(T\), exactly \(k\) edges are marked as key edges. For any key edge chosen as the starting edge, determine the number of distinct new trees that can be generated by the above traversal process. Two new trees are considered different if there exists at least one pair of new nodes which are connected by an edge in one tree but not in the other.

Remark: It can be proved that, regardless of which key edge is chosen as the starting edge, the number of distinct new trees produced by the DFS process is given by

[ \prod_{v=1}^{n} (\deg(v)-1)! \mod (10^9+7), ]

where \(\deg(v)\) is the degree of vertex \(v\) in the original tree \(T\), and by convention \(0! = 1\). Since the answer may be very large, output it modulo \(10^9+7\).

inputFormat

The input is given as follows:

 n k
 u1 v1
 u2 v2
 ...
 u{n-1} v{n-1}
 b1 b2 ... bk

Here, \(n\) (\(2 \le n \le 10^5\)) is the number of nodes in the tree, and \(k\) (\(1 \le k \le n-1\)) is the number of key edges. Each of the next \(n-1\) lines contains two integers \(u_i\) and \(v_i\) (\(1 \le u_i,v_i \le n\), \(u_i \neq v_i\)) representing an edge. The last line contains \(k\) distinct integers \(b_1,b_2,\dots,b_k\) (each between \(1\) and \(n-1\)) indicating the indices (1-indexed, in the order given in the input) of the key edges. It is guaranteed that the given edges form a tree.

outputFormat

Output a single integer, the number of distinct new trees possible when starting the traversal from any key edge, taken modulo \(10^9+7\).

sample

3 1
1 2
2 3
1

1