룰렛

종영이가 오랜 기간 동안 준비한 "옥토끼나라 놀이공원"이 곧 개장을 앞두고 있다. 이 놀이공원에는 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^8)

그 다음 N-1개의 줄에 한 줄에 하나씩 u, v, p_1, p_2가 주어진다. 이는 u번 놀이기구와 v번 놀이기구를 잇는 도로가 있다는 뜻이다. u번 놀이기구의 룰렛에서 v번 놀이기구로 가는 결과가 나오는 칸의 수는 p_1이고, v번 놀이기구의 룰렛에서 u번 놀이기구로 가는 결과가 나오는 칸의 수는 p_2다. (1 ≤ p_1 < A_u, 1 ≤ p_2 < 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^9+6$ 이하의 정수 V를 출력한다. 입력 제약 조건을 만족하는 모든 입력에서 이러한 V가 유일하게 존재함을 증명할 수 있다.