Tree Edge Orientation

Given a tree with N nodes labeled from 1 to N and N − 1 undirected edges, along with M pairs of nodes \((a_i, b_i)\) (for \(1 \le i \le M\)), you are to assign a direction to each edge. The assignment must satisfy that for every given pair \((a_i, b_i)\), either there exists a directed path from \(a_i\) to \(b_i\) or from \(b_i\) to \(a_i\) in the resulting directed graph.

The unique undirected path connecting \(a_i\) and \(b_i\) must have all edges oriented in the same direction (either all in the direction from \(a_i\) to \(b_i\) or all from \(b_i\) to \(a_i\)). Calculate the number of different ways to direct the edges such that all constraints are satisfied. Since the answer can be quite large, output your result modulo \(10^9+7\).

Hint: For each constraint, if the unique path in the tree is composed of \(k\) edges, they must all share the same binary assignment. If some edges do not appear in any constraint, they can be assigned arbitrarily.

Note: All formulas are given in LaTeX format. For example, modulo is written as \(10^9+7\).

inputFormat

The first line contains two integers N and M separated by a space.

The next N − 1 lines each contain two integers u and v, denoting an undirected edge between nodes u and v.

The following M lines each contain two integers a and b representing a constraint pair.

\(1 \le u,v,a,b \le N\)

outputFormat

Output a single integer which is the number of valid ways to assign directions to the tree edges, modulo \(10^9+7\).

sample

3 1
1 2
2 3
1 3

2