E. Expected Distance
time limit per test
4 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Given are two integer sequences: $$$\{a_i\}$$$ of length $$$N - 1$$$ and $$$\{c_i\}$$$ of length $$$N$$$. Let us build a tree $$$T_{N}$$$ with $$$N$$$ vertices in the following way:

  • $$$T_{1}$$$ is a tree made up of only vertex $$$1$$$.
  • For $$$i \gt 1$$$, $$$T_{i}$$$ connects vertex $$$i$$$ to one of the vertices of $$$T_{i - 1}$$$. The probability that vertex $$$j$$$ will be chosen is $$$\displaystyle \frac{a_j}{a_1 + \cdots + a_{i - 1}}$$$. The length of the added edge is then calculated as $$$c_i + c_j$$$.
  • When $$$T_{N}$$$ is built, the process stops.

You are given $$$Q$$$ queries. Each query is a pair of vertices. For each query $$$(u, v)$$$, calculate the expected distance between $$$u$$$ and $$$v$$$ in $$$T_{N}$$$.

Input

The first line of input contains two integers $$$N$$$ and $$$Q$$$: the number of vertices and the number of queries, respectively ($$$2 \leq N, Q \leq 3 \cdot 10^5$$$).

The second line contains $$$N - 1$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{N - 1}$$$ ($$$1 \leq a_i \leq 2000$$$).

The third line contains $$$N$$$ integers $$$c_1$$$, $$$c_2$$$, $$$\ldots$$$, $$$c_N$$$ ($$$1 \leq c_i \leq 2000$$$).

Each of the following $$$Q$$$ lines describes one query and contains two integers $$$u$$$ and $$$v$$$ separated by a space: numbers of vertices to find the expected distance ($$$1 \leq u, v \leq N$$$).

Output

It can be proven that each answer is a rational number and can be written in the form $$$\mathit{ans}_i = \frac{p_i}{q_i}$$$, where $$$p_i$$$ and $$$q_i$$$ are coprime non-negative integers and $$$0 \lt q_i \lt 10^9 + 7$$$. For each query, print the integer $$$(p_i \cdot q_i^{-1}) \bmod (10^9 + 7)$$$.

Examples
Input
5 7
1 1 1 1
1 2 4 8 16
1 3
2 5
4 3
1 5
3 3
4 5
1 2
Output
7
666666697
15
666666697
0
333333366
3
Input
5 4
17 19 23 29
2 3 5 7 11
1 2
3 4
5 2
3 5
Output
5
927495315
106531441
450222593