题目描述

小可可在出题。

小可可需要造一颗树，她不想写很多代码于是决定直接摆烂，第 $ i(i > 1)$ 个点的父亲直接在 $[1, i − 1]$ 之间随机。

后来小可可觉得树太矮了，就决定给每个点加两个权值 $a_i, b_i$，之后第 $i$ 个点的父亲在 $[1, i − 1]$之间以正比与 $a$ 的概率随机，即第 $j(1 \le j < i)$ 个点作为第 i 个点父亲的概 率是 $\frac{a_j}{a_1+a_2+···+a_{i−1}}$，且边 $(j, i)$ 的长度为 $ b_i + b_j$。

小可可很好奇这棵树的结构。于是她给出了 $q$ 次询问，每次给定 $u, v$，询问 $u, v$ 的期望距离对 $10^9 + 7$ 取模的结果。

输入格式

第一行两个整数 $n, q$，表示树节点个数和询问次数。

接下来一行 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。 接下来一行 $n$ 个整数，第 $i$ 个整数表示 $b_i$。 接下来 $q$ 行每行两个整数 $u, v$，表示询问 $u, v$ 期望距离。

输出格式

输出 $q$ 行，表示对应询问的答案。

样例1输入

5 7
1 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