Problem
フォミンのギャングは n 個のグループで構成されており、各グループには ai 人がいます。 q 襲撃が計画されています。 i 番目の襲撃には、各グループから正確に 1 人のローグがいて、その番号はセグメント \([l_i, r_i]\) にあります。 ;
メレホフは悲しいので、襲撃ごとに可能なユニットの数を
\(10^9 + 7\) を法として計算することにしました。しかし、グレゴリーは常に人生の意味を考え、真実を探しているため、計算に集中できず、あなたに助けを求めます.
入力
最初の行は数値 n (\(1 <= n <= 10^5\)) –フォミンのギャングのグループ数。
2 行目に n 個の自然数 ai (\(1 <= a_i <= 2\) ) – i- 番目のグループの人数。
3 行目には q という数字が含まれています –襲撃の数。
以下は q 行で、それぞれに 2 つの数字が含まれています – li と ri (\(1 <= l_i <= r_i <= n\)) – i-th raid
に参加しているグループの数。
出力
q の数値をそれぞれ別の行に出力 –タスクへの応答。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |