باندهای فومین شماره 2
Problem
باند فومین از گروه n تشکیل شده است که هر کدام ai نفر دارند. حملات q برنامه ریزی شده است. حمله i-امین دقیقاً یک دزد از هر گروه را شامل می شود که تعداد آنها در بخش \([l_i, r_i]\).
ملخوف غمگین است، بنابراین برای هر حمله تصمیم گرفت تعداد واحدهای ممکن را محاسبه کند
\(10^9 + 7\). با این حال، گریگوری دائماً به معنای زندگی و جستجوی حقیقت فکر می کند، بنابراین نمی تواند روی محاسبات تمرکز کند و از شما کمک می خواهد.
ورودی
خط اول حاوی عدد
n (
\(1 <= n <= 10^5\)) – تعداد گروه های باند فومین.
خط دوم حاوی
n اعداد طبیعی
ai (
\(1 <= a_i < = 10^6\)) – تعداد افراد در گروه
i-امین.
خط سوم شامل عدد
q – تعداد حملات.
خطوط زیر
q هستند که هر کدام شامل دو عدد –
li و
ri (
\(1 <= l_i <= r_i <= n\)) – تعداد گروه های شرکت کننده در حمله
i-.
حصر
چاپ اعداد
q، هر کدام در یک خط جداگانه – پاسخ به کار
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |