시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 (언어별 추가 시간 없음) 1024 MB 14 9 8 61.538%

문제

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

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

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

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

입력

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

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

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

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

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

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

출력

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

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

예제 입력 1

2 4
2 3
1 2 1 1
1 1
1 2
2 1
2 2

예제 출력 1

200000002
800000006
400000003
600000005

1번 놀이기구를 탄 후 집으로 돌아갈 확률은 $\frac{1}{2}$이며, 2번 놀이기구로 이동할 확률도 $\frac{1}{2}$이다. 2번 놀이기구를 탄 후 집으로 돌아갈 확률은 $\frac{2}{3}$이며, 1번 놀이기구로 이동할 확률은 $\frac{1}{3}$이다. 1번 놀이기구에서 출발했을 때 마지막으로 1번 놀이기구를 타고 집으로 돌아갈 확률은 $\frac{1}{2}+\frac{1}{12}+\frac{1}{72}+\cdots = \frac{3}{5}$이다.