On nous donne deux suites d'entiers : $\{a_i\}$ de longueur $N - 1$ et $\{c_i\}$ de longueur $N$. Construisons un arbre $T_N$ à $N$ sommets de la manière suivante :

• $T_1$ est un arbre composé uniquement du sommet 1.
• Pour $i > 1$, $T_i$ connecte le sommet $i$ à l'un des sommets de $T_{i-1}$. La probabilité que le sommet $j$ soit choisi est $\frac{a_j}{a_1 + \dots + a_{i-1}}$. La longueur de l'arête ajoutée est alors calculée comme $c_i + c_j$.
• Lorsque $T_N$ est construit, le processus s'arrête.

Vous recevez $Q$ requêtes. Chaque requête est une paire de sommets. Pour chaque requête $(u, v)$, calculez la distance espérée entre $u$ et $v$ dans $T_N$.

Entrée

La première ligne de l'entrée contient deux entiers $N$ et $Q$ : le nombre de sommets et le nombre de requêtes, respectivement ($2 \le N, Q \le 3 \cdot 10^5$).

La deuxième ligne contient $N - 1$ entiers $a_1, a_2, \dots, a_{N-1}$ ($1 \le a_i \le 2000$).

La troisième ligne contient $N$ entiers $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 2000$).

Chacune des $Q$ lignes suivantes décrit une requête et contient deux entiers $u$ et $v$ séparés par un espace : les numéros des sommets pour lesquels trouver la distance espérée ($1 \le u, v \le N$).

Sortie

Il peut être prouvé que chaque réponse est un nombre rationnel et peut être écrite sous la forme $ans_i = \frac{p_i}{q_i}$, où $p_i$ et $q_i$ sont des entiers non négatifs premiers entre eux et $0 < q_i < 10^9 + 7$. Pour chaque requête, affichez l'entier $(p_i \cdot q_i^{-1}) \pmod{10^9 + 7}$.

Exemples

Entrée 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

Sortie 1

7
666666697
15
666666697
0
333333366
3

Entrée 2

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

Sortie 2

5
927495315
106531441
450222593