무작위 산책 기대 시간

젊은 정보학도 Kile은 살을 빼야 해서 Sljeme 산으로 떠나기로 했다. 등산 지도를 살펴보던 Kile은 Sljeme의 등산로가 나무 구조를 이룬다는 것을 알아냈다. 더 정확히는 등산로를 트리의 간선으로, 등산로가 만나는 지점을 정점으로 나타냈다.

트리는 자연수 1부터 n까지로 번호를 붙인 n개의 정점으로 이루어져 있다. 그리고 q번의 산행을 계획했는데, i번째 산행은 정점 $a_i$에서 시작해 정점 $b_i$에서 끝난다. 또한 인접한 두 정점 사이의 거리를 정확히 1분에 이동한다고 다소 낙관적으로 추정했다.

그러나 Kile은 방향 감각이 그리 뛰어나지 않다. 그래서 어떤 정점에 도착하면 그 정점을 끝점으로 하는 등산로 중 하나를 균등한 확률로 무작위로 선택해 다음 등산로로 들어선다. Kile은 앞으로의 활동을 계획하기 위해 q번의 산행 각각에 대해 Sljeme을 오르내리며 보낼 기대 시간을 알고 싶어 한다. 즉, 위에서 설명한 방식으로 이동할 때 정점 $a_i$에서 정점 $b_i$까지 이동하는 데 걸리는 기대 시간(분)을 알고 싶어 한다. 그를 도와주자!

참고: 구하는 기대 시간은 기약분수 $P/R$로 나타낼 수 있음을 증명할 수 있다. 정밀도 문제를 피하기 위해 $P \cdot R^{-1} \pmod{10^9 + 7}$을 출력해야 한다.

첫째 줄에 자연수 $n$ ($2 \le n \le 300\,000$)과 $q$ ($1 \le q \le 300\,000$)가 주어진다.

다음 $n - 1$개 줄에 정점 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$)가 주어지며, 이는 번호 $u_i$와 $v_i$인 정점이 간선으로 직접 연결되어 있음을 뜻한다. 간선들은 $n$개 정점으로 이루어진 트리(사이클이 없는 단순 연결 그래프)를 이룬다.

다음 $q$개 줄 중 i번째 줄에 서로 다른 수 $a_i$와 $b_i$ ($1 \le a_i, b_i \le n$)가 주어지며, 이는 i번째 산행의 시작점과 끝점이다.

i번째 줄에 문제에서 설명한 대로 i번째 산행의 기대 소요 시간을 출력한다.