거리의 기댓값

$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 \leq N,Q \leq 300\\,000)$

두 번째 줄에 $N-1$개의 정수 $a\_1,a\_2, \cdots, a\_{N-1}$이 공백으로 구분되어 주어진다. $(1 \leq a\_i \leq 2\\,000)$

세 번째 줄에 $N$개의 정수 $c\_1,c\_2, \cdots, c\_N$이 공백으로 구분되어 주어진다. $(1 \leq c\_i \leq 2\\,000)$

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

$i$번째 쿼리의 답을 $ans\_i=\frac{p\_i}{q\_i}$라 하자. ($p\_i$, $q\_i$는 서로소인 음이 아닌 정수) $i$번째 줄에는 $p\_i \equiv q\_i x\_i \pmod{10^9+7}$를 만족하는 $0$ 이상 $10^9+7$ 미만의 정수 $x\_i$를 출력한다. 이 수는 유일하게 존재함을 증명할 수 있다.