長さ $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 + \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$)。

2行目には $N-1$ 個の整数 $a_1, a_2, \dots, a_{N-1}$ が含まれます ($1 \le a_i \le 2000$)。

3行目には $N$ 個の整数 $c_1, c_2, \dots, c_N$ が含まれます ($1 \le c_i \le 2000$)。

続く $Q$ 行の各行は1つのクエリを表し、スペースで区切られた2つの整数 $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