São dadas duas sequências de inteiros: $\{a_i\}$ de comprimento $N-1$ e $\{c_i\}$ de comprimento $N$. Vamos construir uma árvore $T_N$ com $N$ vértices da seguinte forma:

• $T_1$ é uma árvore constituída apenas pelo vértice $1$.
• Para $i>1$, $T_i$ liga o vértice $i$ a um dos vértices de $T_{i-1}$. A probabilidade de o vértice $j$ ser escolhido é $\frac{a_j}{a_1+\cdots+a_{i-1}}$. O comprimento da aresta acrescentada é então calculado como $c_i+c_j$.
• Quando $T_N$ estiver construída, o processo termina.

São dadas $Q$ consultas. Cada consulta é um par de vértices. Para cada consulta $(u,v)$, calcule a distância esperada entre $u$ e $v$ em $T_N$.

Entrada

A primeira linha da entrada contém dois inteiros $N,Q$: o número de vértices e o número de consultas, respetivamente ($2 \le N,Q \le 3\cdot10^5$).

A segunda linha contém $N-1$ inteiros $a_1,a_2,\ldots,a_{N-1}$ ($1 \le a_i \le 2000$).

A terceira linha contém $N$ inteiros $c_1,c_2,\ldots,c_N$ ($1 \le c_i \le 2000$).

Cada uma das $Q$ linhas seguintes descreve uma consulta e contém dois inteiros $u,v$ separados por um espaço: os números dos vértices cuja distância esperada se pretende encontrar ($1 \le u,v \le N$).

Saída

Pode provar-se que cada resposta é um número racional e pode ser escrita na forma $ans_i=\frac{p_i}{q_i}$, onde $p_i$ e $q_i$ são inteiros não negativos primos entre si e $0<q_i<10^9+7$. Para cada consulta, imprima o inteiro $(p_i\cdot q_i^{-1})\bmod(10^9+7)$.

Exemplos

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

Saída 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

Saída 2

5
927495315
106531441
450222593