거리의 기댓값

$N$개의 정점으로 이루어진 트리 $T_{N}$을 다음과 같은 방법으로 생성한다.

• $T_{1}$은 1번 정점만으로 이루어진 트리다.
• 2 이상의 $i$에 대해 $T_{i}$는 $T_{i-1}$에 $i$번 정점을 추가하고, 이를 $T_{i-1}$의 정점 중 하나와 간선으로 이은 트리다. $i$번 정점이 $j$번 정점과 연결될 확률은 $\frac{a_j}{a_1+ \cdots + a_{i-1}}$이다. $i$번 정점이 $j$번 정점과 연결되었다면 그 간선의 길이는 $c_i + c_j$이다.

$Q$개의 쿼리가 주어진다. 각 쿼리마다 $u$와 $v$가 주어지면, $T_{N}$에서 $u$번 정점과 $v$번 정점 사이 거리의 기댓값을 구하라.

첫 번째 줄에 $N$과 $Q$가 주어진다. $(2 \le N, Q \le 300\,000)$

두 번째 줄에 $N-1$개의 정수 $a_1, a_2, \cdots, a_{N-1}$이 공백으로 구분되어 주어진다. $(1 \le a_i \le 2\,000)$

세 번째 줄에 $N$개의 정수 $c_1, c_2, \cdots, c_N$이 공백으로 구분되어 주어진다. $(1 \le c_i \le 2\,000)$

이후 $Q$개의 줄에 걸쳐 각 줄에 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N)$

$i$번째 쿼리의 답을 $ans_i=\frac{p_i}{q_i}$라 하자. 여기서 $p_i$와 $q_i$는 서로소인 음이 아닌 정수이다. $i$번째 줄에는 $0$ 이상 $10^9+7$ 미만의 정수 $x_i$이며 $p_i \equiv q_i x_i \pmod{10^9+7}$를 만족하는 값을 출력한다. 이 수는 유일하게 존재함을 증명할 수 있다.