畀出兩個整數序列：長度為 $N-1$ 嘅 $\{a_i\}$，同長度為 $N$ 嘅 $\{c_i\}$。我哋按以下方式建立一棵有 $N$ 個頂點嘅樹 $T_N$：

• $T_1$ 係一棵只有頂點 $1$ 嘅樹。
• 對 $i>1$，$T_i$ 會將頂點 $i$ 連到 $T_{i-1}$ 嘅其中一個頂點。頂點 $j$ 被揀中嘅機率係 $\frac{a_j}{a_1+\cdots+a_{i-1}}$。新增邊嘅長度係 $c_i+c_j$。
• 建立好 $T_N$ 之後，過程就結束。

畀出 $Q$ 次查詢，每次查詢係一對頂點。對每次查詢 $(u,v)$，計算 $T_N$ 入面 $u$ 同 $v$ 之間距離嘅期望值。

輸入格式

輸入第一行有兩個整數 $N,Q$，分別係頂點數目同查詢數目（$2 \le N,Q \le 3\cdot 10^5$）。

第二行有 $N-1$ 個整數 $a_1,a_2,\ldots,a_{N-1}$（$1 \le a_i \le 2000$）。

第三行有 $N$ 個整數 $c_1,c_2,\ldots,c_N$（$1 \le c_i \le 2000$）。

之後 $Q$ 行，每行描述一次查詢，包含兩個以空格分隔嘅整數 $u,v$，係要求期望距離嘅頂點編號（$1 \le u,v \le N$）。

輸出格式

可以證明，每個答案都係有理數，可以寫成 $ans_i=\frac{p_i}{q_i}$，其中 $p_i,q_i$ 係互質嘅非負整數，且 $0<q_i<10^9+7$。對每次查詢，輸出整數 $(p_i\cdot q_i^{-1})\bmod(10^9+7)$。

樣例

輸入格式 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

輸出格式 1

7
666666697
15
666666697
0
333333366
3

輸入格式 2

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

輸出格式 2

5
927495315
106531441
450222593