נתונות שתי סדרות של מספרים שלמים: $\{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