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