给定两个整数序列：长度为 $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$)。 第二行包含 $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