Cho hai dãy số nguyên: $\{a_i\}$ có độ dài $N - 1$ và $\{c_i\}$ có độ dài $N$. Hãy xây dựng một cây $T_N$ với $N$ đỉnh theo cách sau:

• $T_1$ là một cây chỉ gồm đỉnh 1.
• Với $i > 1$, $T_i$ nối đỉnh $i$ vào một trong các đỉnh của $T_{i-1}$. Xác suất để đỉnh $j$ được chọn là $\frac{a_j}{a_1 + \dots + a_{i-1}}$. Độ dài của cạnh được thêm vào được tính bằng $c_i + c_j$.
• Khi $T_N$ được xây dựng xong, quá trình dừng lại.

Bạn được cho $Q$ truy vấn. Mỗi truy vấn là một cặp đỉnh. Với mỗi truy vấn $(u, v)$, hãy tính khoảng cách kỳ vọng giữa $u$ và $v$ trong $T_N$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $N$ và $Q$: số lượng đỉnh và số lượng truy vấn ($2 \le N, Q \le 3 \cdot 10^5$).

Dòng thứ hai chứa $N - 1$ số nguyên $a_1, a_2, \dots, a_{N-1}$ ($1 \le a_i \le 2000$).

Dòng thứ ba chứa $N$ số nguyên $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 2000$).

Mỗi dòng trong $Q$ dòng tiếp theo mô tả một truy vấn và chứa hai số nguyên $u$ và $v$ cách nhau bởi một dấu cách: số hiệu của các đỉnh cần tính khoảng cách kỳ vọng ($1 \le u, v \le N$).

Dữ liệu ra

Có thể chứng minh rằng mỗi câu trả lời là một số hữu tỉ và có thể viết dưới dạng $ans_i = \frac{p_i}{q_i}$, trong đó $p_i$ và $q_i$ là các số nguyên không âm nguyên tố cùng nhau và $0 < q_i < 10^9 + 7$. Với mỗi truy vấn, hãy in ra số nguyên $(p_i \cdot q_i^{-1}) \pmod{10^9 + 7}$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

7
666666697
15
666666697
0
333333366
3

Dữ liệu vào 2

5 4
17 19 23 29
2 3 5 7 11
1 2
3 4
5 2
3 5

Dữ liệu ra 2

5
927495315
106531441
450222593