Dane są dwa ciągi liczb całkowitych: $\{a_i\}$ o długości $N - 1$ oraz $\{c_i\}$ o długości $N$. Skonstruujmy drzewo $T_N$ o $N$ wierzchołkach w następujący sposób:

• $T_1$ to drzewo składające się tylko z wierzchołka 1.
• Dla $i > 1$, $T_i$ łączy wierzchołek $i$ z jednym z wierzchołków drzewa $T_{i-1}$. Prawdopodobieństwo, że zostanie wybrany wierzchołek $j$, wynosi $\frac{a_j}{a_1 + \dots + a_{i-1}}$. Długość dodanej krawędzi jest obliczana jako $c_i + c_j$.
• Gdy $T_N$ zostanie zbudowane, proces się kończy.

Otrzymujesz $Q$ zapytań. Każde zapytanie to para wierzchołków. Dla każdego zapytania $(u, v)$ oblicz oczekiwaną odległość między $u$ oraz $v$ w $T_N$.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $N$ oraz $Q$: odpowiednio liczbę wierzchołków oraz liczbę zapytań ($2 \le N, Q \le 3 \cdot 10^5$).

Druga linia zawiera $N - 1$ liczb całkowitych $a_1, a_2, \dots, a_{N-1}$ ($1 \le a_i \le 2000$).

Trzecia linia zawiera $N$ liczb całkowitych $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 2000$).

Każda z kolejnych $Q$ linii opisuje jedno zapytanie i zawiera dwie liczby całkowite $u$ oraz $v$ oddzielone spacją: numery wierzchołków, dla których należy znaleźć oczekiwaną odległość ($1 \le u, v \le N$).

Wyjście

Można udowodnić, że każda odpowiedź jest liczbą wymierną i może zostać zapisana w postaci $ans_i = \frac{p_i}{q_i}$, gdzie $p_i$ oraz $q_i$ są względnie pierwszymi nieujemnymi liczbami całkowitymi oraz $0 < q_i < 10^9 + 7$. Dla każdego zapytania wypisz liczbę całkowitą $(p_i \cdot q_i^{-1}) \pmod{10^9 + 7}$.

Przykład

Wejście 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

Wyjście 1

7
666666697
15
666666697
0
333333366
3

Wejście 2

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

Wyjście 2

5
927495315
106531441
450222593