給定兩個整數數列：長度為 $N-1$ 的 $\{a_i\}$ 與長度為 $N$ 的 $\{c_i\}$。我們依照下列方式建立一個具有 $N$ 個頂點的樹 $T_N$：

• $T_1$ 是一棵僅由頂點 1 組成的樹。
• 對於 $i > 1$，將頂點 $i$ 連接到 $T_{i-1}$ 中的其中一個頂點。選擇頂點 $j$ 的機率為 $\frac{a_j}{a_1 + \dots + 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, \dots, a_{N-1}$ ($1 \le a_i \le 2000$)。 第三行包含 $N$ 個整數 $c_1, c_2, \dots, 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}) \pmod{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