Даны две целочисленные последовательности: $\{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 + \dots + 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, \dots, a_{N-1}$ ($1 \le a_i \le 2000$).

Третья строка содержит $N$ целых чисел $c_1, c_2, \dots, 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}) \pmod{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

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

5
927495315
106531441
450222593