Problem
Geng Fomin terdiri daripada kumpulan n, setiap satunya mempunyai ai orang. serbuan q telah dirancang. Serbuan ke iakan mempunyai seorang penyangak daripada setiap kumpulan yang bilangannya terletak dalam segmen \([l_i, r_i]\). ;
Melekhov sedih, jadi untuk setiap serbuan dia memutuskan untuk mengira bilangan unit modulo
\(10^9 + 7\). Walau bagaimanapun, Gregory sentiasa memikirkan tentang erti kehidupan dan mencari kebenaran, jadi dia tidak dapat menumpukan perhatian pada pengiraan dan meminta bantuan anda.
Input
Baris pertama ialah nombor n (\(1 <= n <= 10^5\)) – bilangan kumpulan dalam kumpulan Fomin.
Baris kedua mengandungi n nombor asli ai (\(1 <= a_i <= 2\) ) – bilangan orang dalam i-kumpulan ke.
Baris ketiga mengandungi nombor q – bilangan serbuan.
Berikut ialah baris q, setiap satu mengandungi dua nombor – li dan ri (\(1 <= l_i <= r_i <= n\)) – bilangan kumpulan yang mengambil bahagian dalam serbuan i-.
Output
Output
q nombor, setiap satu pada baris berasingan – tindak balas terhadap tugasan.
Contoh
| # |
Input |
Output |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |