กำหนดลำดับจำนวนเต็มสองลำดับ ได้แก่ $\{a_i\}$ ความยาว $N-1$ และ $\{c_i\}$ ความยาว $N$ มาสร้างต้นไม้ $T_N$ ที่มีจุดยอด $N$ จุดด้วยวิธีต่อไปนี้:

• $T_1$ เป็นต้นไม้ที่มีเพียงจุดยอด $1$
• สำหรับ $i>1$ ต้นไม้ $T_i$ เชื่อมจุดยอด $i$ เข้ากับจุดยอดหนึ่งใน $T_{i-1}$ ความน่าจะเป็นที่จะเลือกจุดยอด $j$ คือ $\frac{a_j}{a_1+\cdots+a_{i-1}}$ จากนั้นกำหนดความยาวเส้นเชื่อมที่เพิ่มเป็น $c_i+c_j$
• เมื่อสร้าง $T_N$ แล้ว กระบวนการจะหยุด

กำหนดคำถาม $Q$ ข้อมาให้ แต่ละคำถามเป็นคู่ของจุดยอด สำหรับแต่ละคำถาม $(u,v)$ จงคำนวณค่าคาดหมายของระยะห่างระหว่าง $u$ และ $v$ ใน $T_N$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองจำนวน $N$ และ $Q$ ซึ่งเป็นจำนวนจุดยอดและจำนวนคำถามตามลำดับ ($2 \le N,Q \le 3\cdot 10^5$)

บรรทัดที่สองมีจำนวนเต็ม $N-1$ จำนวน $a_1,a_2,\ldots,a_{N-1}$ ($1 \le a_i \le 2000$)

บรรทัดที่สามมีจำนวนเต็ม $N$ จำนวน $c_1,c_2,\ldots,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})\bmod(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