تتكون عصابة فومين من مجموعات n ، كل منها بها a i أشخاص. تم التخطيط لغارات q . سيكون للغارة i محتالة واحدة بالضبط من كل مجموعة يقع رقمها في المقطع \ ([l_i، r_i] \) . & nbsp ؛
ميليخوف حزين ، لذلك قرر في كل غارة حساب عدد الوحدات الممكنة modulo
\ (10 ^ 9 + 7 \) . ومع ذلك ، يفكر جريجوري باستمرار في معنى الحياة ويبحث عن الحقيقة ، لذلك لا يمكنه التركيز على الحسابات ويطلب منك المساعدة.
إدخال
السطر الأول عبارة عن رقم n ( \ (1 & lt؛ = n & lt؛ = 10 ^ 5 \) ) & ndash؛ عدد & nbsp؛ المجموعات في عصابة فومين.
يحتوي السطر الثاني على n أعداد طبيعية
a i (
\ (1 & lt؛ = a_i & lt؛ = 2 \) ) & ndash؛ عدد الأشخاص في المجموعة i- الخامسة.
يحتوي السطر الثالث على الرقم
q & ndash؛ عدد المداهمات.
فيما يلي q سطور ، كل منها يحتوي على رقمين & ndash؛ l i و r i ( \ (1 & lt؛ = l_i & lt؛ = r_i & lt؛ = n \) ) & ndash؛ عدد المجموعات المشاركة في i- الغارة.
الإخراج
إخراج أرقام
q ، كل منها في سطر منفصل & ndash؛ استجابة للمهمة.
نبسب ؛
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |