Gangs de Fomine
Problem
Le gang de Fomin se compose de n groupes, dont chacun a ai personnes. Des raids q sont prévus. Le ith raid aura exactement un voleur de chaque groupe dont le nombre se situe dans le segment \([l_i, r_i]\). ;
Melekhov est triste, alors pour chaque raid, il a décidé de calculer le nombre d'unités possibles modulo
\(10^9 + 7\). Cependant, Gregory pense constamment au sens de la vie et à la recherche de la vérité, il ne peut donc pas se concentrer sur les calculs et vous demande de l'aide.
Entrée
La première ligne est un nombre n (\(1 <= n <= 10^5\)) – le nombre de groupes dans le gang de Fomin.
La deuxième ligne contient n nombres naturels ai (\(1 <= a_i <= 2\) ) – nombre de personnes dans le i-ème groupe.
La troisième ligne contient le nombre q – nombre de raids.
Ce qui suit sont des lignes q, chacune contenant deux nombres – li et ri (\(1 <= l_i <= r_i <= n\)) – nombre de groupes participant au i-ème raid.
Sortie
Sortir des numéros
q, chacun sur une ligne distincte – réponse à la tâche.
Exemples
| # |
Entrée |
Sortie |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
2
1
8 |