تُعطى متتاليتان من الأعداد الصحيحة: $\{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 \cdot 10^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$.

الإخراج

يمكن إثبات أن كل إجابة عدد نسبي يمكن كتابته بالشكل $\mathrm{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