B. 【GENOIP#41】名字

题目描述

小可可在出题。

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

后来小可可觉得树太矮了，就决定给每个点加两个权值 $a_i,b_i$ ，之后第 $i$ 个点的父亲在 $[1,i-1]$ 之间以正比与 $a$ 的概率随机，即第 $j~(1\leq j<i)$ 个点作为第 $i$ 个点父亲的概率是 $\frac{a_j}{a_1+a_2+\cdots+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

7
666666697
15
666666697
0
333333366
3

数据范围与提示

样例 2/3

样例下载

数据规模与约定

对于 $30\%$ 的数据， $n\leq5$ ；

对于 $50\%$ 的数据， $n\leq10^3$ ；

对于另外 $20\%$ 的数据， $a_i=b_i=1$ ；

对于 $100\%$ 的数据， $2\leq n,q\leq3\times10^5,1\leq a_i,b_i\leq3\times10^3$ 。