길이가 $N-1$인 정수 수열 $\{a_i\}$와 길이가 $N$인 정수 수열 $\{c_i\}$가 주어집니다. 다음과 같은 방식으로 $N$개의 정점을 가진 트리 $T_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)$로 구성됩니다. 각 쿼리에 대해 $T_N$에서 $u$와 $v$ 사이의 기대 거리를 계산하십시오.

입력

첫 번째 줄에는 정점의 개수 $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

예제 출력 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