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