G. Howl's Moving Castle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sophie has found herself trapped inside Howl's Moving Castle!

Howl's Moving Castle can be represented as a connected graph of $$$N$$$ rooms and $$$N-1$$$ (bidirectional) hallways connecting rooms. However, this isn't just any old castle – this is Howl's Moving Castle. Every morning, the castle comes to life, and the rooms shift such that some of the hallways become inaccessible, disconnecting the rooms adjacent to the hallways. This creates a distinct partition of rooms – a grouping of rooms into non-empty subsets such that each room is in exactly one subset, each subset forms a connected graph, and the subsets are disconnected from each other.

Sophie has a set of possible tasks (reload the trebuchets, feed the alligators in the moat, empty the chamber pot, etc.), which requires moving between two rooms. Specifically, for the $$$t$$$th task, Sophie starts at room $$$a_t$$$, and needs the path to the second room $$$b_t$$$ to be unobstructed.

How many possible partitions of Howl's Moving Castle are there such that every task can be completed?

You can assume that Sophie can teleport between tasks, i.e. teleport from room $$$b_t$$$ to room $$$a_{t+1}$$$.

Input

The first line contains two integers $$$N$$$, $$$T$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le T \le 10^5$$$) denoting the number of rooms in the castle and the number of tasks, respectively.

The next $$$N-1$$$ lines contain two integers $$$u_i, v_i$$$ each, which means that there is a hallway connecting room $$$u_i$$$ to room $$$v_i$$$. ($$$1 \le u_i, v_i \le N, u_i \neq v_i$$$)

The final $$$T$$$ lines contain two integers $$$a_t, b_t$$$ each, which means that the $$$t$$$th task requires an unobstructed path between room $$$a_t$$$ and room $$$b_t$$$. ($$$1 \le a_t, b_t \le N$$$)

Output

Output a single integer, the number of possible partitions of the castle (created by obstructing some hallways) such that every task can be completed. Because this number can be large, output it modulo $$$10^9 + 7$$$.

Example
Input
6 2
1 2
1 3
3 4
3 5
5 6
2 3
5 6
Output
4
Note

In the sample test case, there are four possible partitions:

  • {{1, 2, 3}, {4}, {5, 6}}
  • {{1, 2, 3, 4}, {5, 6}}
  • {{1, 2, 3, 5, 6}, {4}}
  • {{1, 2, 3, 4, 5, 6}}