Se dan dos secuencias de enteros: $\{a_i\}$ de longitud $N - 1$ y $\{c_i\}$ de longitud $N$. Construyamos un árbol $T_N$ con $N$ vértices de la siguiente manera:

• $T_1$ es un árbol compuesto únicamente por el vértice 1.
• Para $i > 1$, $T_i$ conecta el vértice $i$ a uno de los vértices de $T_{i-1}$. La probabilidad de que el vértice $j$ sea elegido es $\frac{a_j}{a_1 + \dots + a_{i-1}}$. La longitud de la arista añadida se calcula entonces como $c_i + c_j$.
• Cuando se construye $T_N$, el proceso se detiene.

Se le dan $Q$ consultas. Cada consulta es un par de vértices. Para cada consulta $(u, v)$, calcule la distancia esperada entre $u$ y $v$ en $T_N$.

Entrada

La primera línea de la entrada contiene dos enteros $N$ y $Q$: el número de vértices y el número de consultas, respectivamente ($2 \le N, Q \le 3 \cdot 10^5$).

La segunda línea contiene $N - 1$ enteros $a_1, a_2, \dots, a_{N-1}$ ($1 \le a_i \le 2000$).

La tercera línea contiene $N$ enteros $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 2000$).

Cada una de las siguientes $Q$ líneas describe una consulta y contiene dos enteros $u$ y $v$ separados por un espacio: los números de los vértices para encontrar la distancia esperada ($1 \le u, v \le N$).

Salida

Se puede demostrar que cada respuesta es un número racional y puede escribirse en la forma $ans_i = \frac{p_i}{q_i}$, donde $p_i$ y $q_i$ son enteros no negativos coprimos y $0 < q_i < 10^9 + 7$. Para cada consulta, imprima el entero $(p_i \cdot q_i^{-1}) \pmod{10^9 + 7}$.

Ejemplos

Entrada 1

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

Salida 1

7
666666697
15
666666697
0
333333366
3

Entrada 2

5 4
17 19 23 29
2 3 5 7 11
1 2
3 4
5 2
3 5

Salida 2

5
927495315
106531441
450222593