17376번 - 룰렛

종영이가 오랜 기간 동안 준비한 "옥토끼나라 놀이공원"이 곧 개장을 앞두고 있다. 이 놀이공원에는 N개의 놀이기구가 있고, 두 놀이기구 사이를 잇는 도로들이 N-1개 있다. 사람들은 이 도로들을 이용해 자신이 있는 놀이기구에서 다른 원하는 놀이기구로 반드시 이동할 수 있다. 또한 이 놀이공원에는 다음에 어떤 놀이기구를 탈지 고민하는 사람들을 위해 종영이의 야심작 "룰렛 시스템"이 도입되었다.

놀이공원의 각 놀이기구 옆에는 룰렛이 하나씩 있다. 룰렛은 여러 칸으로 나뉘어 있고, 각 칸에는 현재 놀이기구와 도로로 직접 연결된 다른 놀이기구나 집이 그려져 있다. 룰렛은 아주 정확해서 어떤 그림이 나올 확률은 그 그림이 그려진 칸의 수와 비례한다. 놀이기구를 타고 나온 사람들은 이 룰렛을 돌려서 다른 놀이기구가 나오면 그 놀이기구로 이동하고, 집이 나오면 더 이상 놀이기구를 타지 않고 집으로 돌아간다.

종영이는 더 많은 수익을 얻고자 놀이기구를 하나 골라서 그 옆에 식당을 짓기로 했다. 사람들은 집으로 돌아가기 전까지는 계속해서 놀이기구를 타기 때문에, 이 놀이기구를 끝으로 더 이상 놀이기구를 타지 않고 집에 돌아가는 사람이 많을수록 식당은 더 큰 수익을 낼 수 있을 것이다. 종영이는 식당이 낼 수 있는 수익이 너무 작다면 놀이공원의 입구를 바꾸는 것까지도 고려하고 있다.

따라서 식당과 입구의 위치를 잘 정하기 위해서는 입구로 들어온 사람이 식당 옆에 있는 놀이기구를 타고 나서 집에 돌아갈 확률을 구해야 한다. 종영이를 위해 두 개의 놀이기구의 번호 S, E가 주어지면 S번 놀이기구에서 출발했을 때 마지막으로 E번 놀이기구를 타고 집으로 돌아갈 확률을 구해주자.

첫 줄에 놀이기구의 수 N과 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ Q ≤ 500,000)

그 후 N개의 수가 주어지는데, i번째 수 A_i는 i번 놀이기구의 룰렛의 칸 수를 의미한다. (2 ≤ A_i ≤ 10⁸)

그 후 N-1개의 줄에 걸쳐 한 줄에 하나씩 u, v, p₁, p₂가 주어진다. 이는 u번 놀이기구와 v번 놀이기구를 잇는 도로가 있으며, u번 놀이기구의 룰렛에서 v번 놀이기구로 가는 결과가 나오는 칸의 수가 p₁이며, v번 놀이기구의 룰렛에서 u번 놀이기구로 가는 결과가 나오는 칸의 수가 p₂라는 뜻이다. (1 ≤ p₁ < A_u, 1 ≤ p₂ < A_v)

도로 정보들로 주어진 i번째 놀이기구에 있는 룰렛의 칸의 수의 합은 A_i 미만임이 보장되며, 합을 S_i라 했을 때 i번째 놀이기구에서 집으로 돌아가는 결과가 나오는 칸의 수는 A_i-S_i개다.

그 후 Q개의 줄에 걸쳐 한 줄에 하나씩 쿼리에 해당하는 S와 E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N)

어떠한 S와 E를 잡아도 쿼리의 답이 $\frac{p}{q}$(p와 q는 서로소인 정수) 꼴이라는 것을 증명할 수 있으며, 이때 $p, q \not\equiv 0 \pmod{10^{9}+7}$임이 보장되는 입력이 주어진다.

i번째 답이 B_i일 때, $B_{i}=$$\frac{P_{i}}{Q_{i}}$ 꼴이라 하자. (P_i와 Q_i는 서로소인 정수)

Q개의 답을 줄바꿈으로 구분하여 출력하는데, i번째 답으로는 $V \cdot$ $Q_{i} \equiv P_{i} \pmod{10^9+7}$을 만족하는 0 이상 10⁹+6이하의 정수 V를 출력한다. 입력 제약 조건을 만족하는 모든 입력에서 이러한 V가 유일하게 존재함을 증명할 수 있다.