Diberikan dua urutan bilangan bulat: $\{a_i\}$ sepanjang $N-1$ dan $\{c_i\}$ sepanjang $N$. Kita akan membangun pohon $T_N$ dengan $N$ simpul sebagai berikut:

• $T_1$ adalah pohon yang hanya terdiri atas simpul $1$.
• Untuk $i > 1$, $T_i$ menghubungkan simpul $i$ ke salah satu simpul pada $T_{i-1}$. Peluang simpul $j$ dipilih adalah $\frac{a_j}{a_1 + \cdots + a_{i-1}}$. Panjang sisi yang ditambahkan kemudian dihitung sebagai $c_i + c_j$.
• Ketika $T_N$ telah dibangun, proses berhenti.

Diberikan $Q$ kueri. Setiap kueri adalah sepasang simpul. Untuk setiap kueri $(u,v)$, hitung nilai harapan jarak antara $u$ dan $v$ pada $T_N$.

Masukan

Baris pertama masukan berisi dua bilangan bulat $N$ dan $Q$: berturut-turut banyaknya simpul dan banyaknya kueri ($2 \le N,Q \le 3 \cdot 10^5$).

Baris kedua berisi $N-1$ bilangan bulat $a_1,a_2,\ldots,a_{N-1}$ ($1 \le a_i \le 2000$).

Baris ketiga berisi $N$ bilangan bulat $c_1,c_2,\ldots,c_N$ ($1 \le c_i \le 2000$).

Setiap dari $Q$ baris berikutnya mendeskripsikan satu kueri dan berisi dua bilangan bulat $u$ dan $v$ yang dipisahkan spasi: nomor simpul yang nilai harapan jaraknya harus dicari ($1 \le u,v \le N$).

Keluaran

Dapat dibuktikan bahwa setiap jawaban adalah bilangan rasional dan dapat ditulis dalam bentuk $ans_i = \frac{p_i}{q_i}$, dengan $p_i$ dan $q_i$ adalah bilangan bulat tak negatif yang relatif prima dan $0 < q_i < 10^9 + 7$. Untuk setiap kueri, cetak bilangan bulat $(p_i \cdot q_i^{-1}) \bmod (10^9 + 7)$.

Contoh

Masukan 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

Keluaran 1

7
666666697
15
666666697
0
333333366
3

Masukan 2

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

Keluaran 2

5
927495315
106531441
450222593