우편 배달

원격 지역의 우편 배달을 자동화하려고 로봇 택배 기사 시스템을 시험하고 있다.

이 지역에는 $n$개의 도시가 있고, $n - 1$개의 양방향 도로로 연결되어 있다. 도로를 따라 어느 도시에서든 다른 모든 도시로 갈 수 있다. 도로로 직접 연결된 두 도시를 서로 인접한 도시라고 한다. 각 도시에 인접한 도시는 최대 $D$개이다. 도시에는 $1$번부터 $n$번까지 번호가 붙어 있으며, $1$번 도시가 수도이다.

각 도시에는 택배 회사의 사무소가 있다. 택배 기사는 $m$개의 소포를 배달해야 한다. $i$번째 소포에는 출발 도시 $a_i$와 도착 도시 $b_i$가 주어진다.

로봇 택배 기사는 다음 알고리즘을 따른다.

• 수도에서 출발해 도로를 따라 도시 사이를 이동한다. 이동하는 동안에는 소포를 몇 개든지 가지고 다닐 수 있다.
• 아직 방문하지 않은 도시에 처음 도착할 때마다 그 도시의 사무소에 들른다. 가지고 있는 소포 중 그 도시가 도착 도시인 소포는 모두 내려놓고, 그 도시가 출발 도시인 소포는 모두 받아 싣는다.
• 현재 도시에 인접한 도시 중 아직 방문하지 않은 도시가 있으면, 그중 하나를 골라 이동한다.
• 인접한 도시를 모두 방문했고 현재 위치가 수도가 아니면, 수도에 가장 가까운 인접 도시로 이동한다. 현재 위치가 수도이면 여행을 마친다.

택배 기사는 각 도시의 사무소에 처음 방문할 때 딱 한 번 들른다. $i$번째 소포는 $a_i$번 도시의 사무소를 $b_i$번 도시의 사무소보다 먼저 방문하면 배달된다.

방문 순서는 다음에 고르는 미방문 인접 도시에 따라 달라질 수 있다. 모든 소포를 배달할 수 있는 방문 순서를 허용 가능한 순서라고 한다.

도로 정보와 배달할 소포 정보가 주어질 때, 허용 가능한 방문 순서의 개수를 $10^9+7$로 나눈 나머지를 구하는 프로그램을 작성하라.

첫째 줄에 도시의 수 $n$과 소포의 수 $m$이 주어진다 ($2 \le n \le 100\,000$, $1 \le m \le 300\,000$).

다음 $n - 1$개의 줄에는 도로 정보가 주어진다. 각 줄에는 $i$번째 도로가 잇는 두 도시의 번호 $u_i$, $v_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

모든 도시는 도로로 서로 오갈 수 있도록 연결되어 있다. 각 도시에서 나가는 도로의 수는 $D$를 넘지 않는다.

다음 $m$개의 줄에는 소포 정보가 주어진다. 각 줄에는 $i$번째 소포의 출발 도시 $a_i$와 도착 도시 $b_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$).

한 줄에 정수 하나를 출력한다. 허용 가능한 방문 순서의 개수를 $10^9+7$로 나눈 나머지이다.

그림은 첫 번째 예시의 도시와 도로를 보여준다. 이 예시에서는 5번 도시에서 3번 도시로, 4번 도시에서 6번 도시로 소포를 배달해야 한다. 다음 방문 순서는 허용 가능하다. 각 사무소를 처음 방문하는 위치는 굵게 표시했다. (1, 4, 1, 2, 5, 2, 6, 2, 1, 3, 1), (1, 4, 1, 2, 6, 2, 5, 2, 1, 3, 1).

두 번째 예시는 같은 도시와 도로를 쓰며, 5번 도시에서 2번 도시로 소포를 배달해야 한다. 이는 불가능하다. 2번 도시를 다시 방문할 때는 사무소에 들르지 않고, 수도에서 출발하는 어떤 경로에서도 2번 도시보다 먼저 5번 도시를 처음 방문할 수 없기 때문이다.