Problem
Le gang de Fomin se compose de n groupes, dont chacun a ai personnes. Des raids q sont prévus. Le i-ième raid comprendra exactement un voleur de chaque groupe dont le numéro 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 réfléchit 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 contient le nombre
n (
\(1 <= n <= 10^5\)) – le nombre de groupes dans le gang de Fomine.
La deuxième ligne contient
n nombres naturels
ai (
\(1 <= a_i < = 10^6\)) – le nombre de personnes dans le
i-ième groupe.
La troisième ligne contient le nombre
q – nombre de raids.
Les lignes suivantes sont
q, chacune contenant deux nombres –
li et
ri (
\(1 <= l_i <= r_i <= n\)) – nombre de groupes participant au
i-ème raid.
Mentions légales
Imprimer les numéros
q, chacun sur une ligne distincte – réponse à la tâche.
Exemples
| # |
Entrée |
Sortie |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |