Gegeben sind zwei ganzzahlige Folgen: $\{a_i\}$ der Länge $N-1$ und $\{c_i\}$ der Länge $N$. Wir bauen einen Baum $T_N$ mit $N$ Knoten wie folgt:

• $T_1$ ist ein Baum, der nur aus Knoten $1$ besteht.
• Für $i>1$ verbindet $T_i$ den Knoten $i$ mit einem der Knoten von $T_{i-1}$. Die Wahrscheinlichkeit, dass Knoten $j$ gewählt wird, beträgt $\frac{a_j}{a_1+\cdots+a_{i-1}}$. Die Länge der hinzugefügten Kante wird als $c_i+c_j$ berechnet.
• Sobald $T_N$ aufgebaut ist, endet der Vorgang.

Gegeben sind $Q$ Anfragen. Jede Anfrage ist ein Knotenpaar. Berechnen Sie für jede Anfrage $(u,v)$ den erwarteten Abstand zwischen $u$ und $v$ in $T_N$.

Eingabe

Die erste Eingabezeile enthält zwei ganze Zahlen $N,Q$, die Anzahl der Knoten beziehungsweise der Anfragen ($2 \le N,Q \le 3\cdot10^5$).

Die zweite Zeile enthält $N-1$ ganze Zahlen $a_1,a_2,\ldots,a_{N-1}$ ($1 \le a_i \le 2000$).

Die dritte Zeile enthält $N$ ganze Zahlen $c_1,c_2,\ldots,c_N$ ($1 \le c_i \le 2000$).

Jede der folgenden $Q$ Zeilen beschreibt eine Anfrage und enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $u,v$: die Nummern der Knoten, deren erwarteter Abstand gesucht ist ($1 \le u,v \le N$).

Ausgabe

Es lässt sich beweisen, dass jede Antwort rational ist und als $ans_i=\frac{p_i}{q_i}$ geschrieben werden kann. Dabei sind $p_i,q_i$ teilerfremde nichtnegative ganze Zahlen mit $0<q_i<10^9+7$. Geben Sie für jede Anfrage die ganze Zahl $(p_i\cdot q_i^{-1})\bmod(10^9+7)$ aus.

Beispiele

Eingabe 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

Ausgabe 1

7
666666697
15
666666697
0
333333366
3

Eingabe 2

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

Ausgabe 2

5
927495315
106531441
450222593