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 [li,ri]. ;
Melekhov sedih, jadi untuk setiap serbuan dia memutuskan untuk mengira bilangan unit modulo
109+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<=105) – bilangan kumpulan dalam kumpulan Fomin.
Baris kedua mengandungi n nombor asli ai (1<=ai<=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<=li<=ri<=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 |