Mail Delivery

A region is testing a robotic courier to automate mail delivery in remote areas.

The region has $n$ cities connected by $n - 1$ two-way roads. Along these roads, you can travel from any city to any other city. Two cities joined by a road are called neighbors. Each city has at most $D$ neighbors. The cities are numbered from $1$ to $n$, and city $1$ is the capital.

Each city has an office of a courier company. The courier must deliver $m$ parcels. The $i$-th parcel has a source city $a_i$ and a destination city $b_i$.

The robot courier follows this procedure.

• It starts in the capital and moves between cities along roads. While moving, it can carry any number of parcels.
• Each time it arrives at a city it has not visited before, it stops at that city's office, leaves every parcel it carries that is addressed to that city, and picks up every parcel that is sent from that city.
• If a neighbor of the current city has not been visited, it picks one such neighbor and moves there.
• If all neighbors have been visited and the courier is not in the capital, it moves to the neighbor closest to the capital. If it is in the capital, the trip ends.

The courier visits each office exactly once, on the first visit. The $i$-th parcel is delivered if the courier visits the office in city $a_i$ before the office in city $b_i$.

The visiting order depends on which unvisited neighbor the courier picks at each step. A visiting order is called valid if every parcel is delivered.

Given the road map and the parcels, count the valid visiting orders. Output the count modulo $10^9+7$.

The first line contains two integers $n$ and $m$, the number of cities and the number of parcels ($2 \le n \le 100\,000$, $1 \le m \le 300\,000$).

Each of the next $n - 1$ lines describes a road with two integers $u_i$ and $v_i$, the cities it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

The roads connect all cities. Each city has at most $D$ roads.

Each of the next $m$ lines describes a parcel with two integers $a_i$ and $b_i$, its source and destination cities ($1 \le a_i, b_i \le n$, $a_i \ne b_i$).

Print one integer: the number of valid visiting orders modulo $10^9+7$.

The figure shows the cities and roads of the first example. Parcels go from city 5 to city 3 and from city 4 to city 6. The following visiting orders are valid. The first visit to each office is in bold: (1, 4, 1, 2, 5, 2, 6, 2, 1, 3, 1) and (1, 4, 1, 2, 6, 2, 5, 2, 1, 3, 1).

In the second example, the cities and roads are the same, and the parcel goes from city 5 to city 2. This is impossible. The courier does not stop at an office on a repeat visit to city 2, and city 5 cannot be visited for the first time before city 2 on any route from the capital.