Expected Distance

Build a tree $T_{N}$ with $N$ vertices as follows.

• $T_{1}$ is a tree that consists only of vertex 1.
• For each $i$ with $2 \le i$, $T_{i}$ is the tree made by adding vertex $i$ to $T_{i-1}$ with an edge to one of the vertices of $T_{i-1}$. The probability that vertex $i$ connects to vertex $j$ is $\frac{a_j}{a_1+ \cdots + a_{i-1}}$. If vertex $i$ connects to vertex $j$, the length of that edge is $c_i + c_j$.

You are given $Q$ queries. For each query with $u$ and $v$, find the expected distance between vertex $u$ and vertex $v$ in $T_{N}$.

The first line contains $N$ and $Q$. $(2 \le N, Q \le 300\,000)$

The second line contains $N-1$ integers $a_1, a_2, \cdots, a_{N-1}$, separated by spaces. $(1 \le a_i \le 2\,000)$

The third line contains $N$ integers $c_1, c_2, \cdots, c_N$, separated by spaces. $(1 \le c_i \le 2\,000)$

Each of the next $Q$ lines contains $u$ and $v$, separated by a space. $(1 \le u, v \le N)$

Let the answer to the $i$-th query be $ans_i=\frac{p_i}{q_i}$, where $p_i$ and $q_i$ are coprime non-negative integers. On the $i$-th line, print the integer $x_i$ with $0 \le x_i < 10^9+7$ that satisfies $p_i \equiv q_i x_i \pmod{10^9+7}$. It can be proven that such $x_i$ is unique.