Задано дві послідовності цілих чисел: $\{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\cdot10^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