Fomins Bande Nr.2
Problem
Die Fomin-Bande besteht aus n Gruppen, in denen jeweils ai eine Person besteht. Es ist geplant, q Razzien durchzuführen. An der i-Runde wird genau ein Räuber aus jeder Gruppe teilnehmen, deren Nummer im Abschnitt \([l_i, r_i]\) liegt.
Melechow sehnt sich danach, weshalb er für jeden Überfall die Anzahl der möglichen Einheiten nach dem Modul
\(10^9 + 7\). Gregor denkt jedoch ständig über den Sinn des Lebens nach und sucht nach der Wahrheit, daher kann er sich nicht auf Berechnungen konzentrieren und bittet Sie um Hilfe.
Eingabe
Die erste Zeile enthält die Zahl n (\(1 <= n <= 10^5\)) – die Anzahl der Gruppen in der Fomin-Bande.
Die zweite Zeile enthält n natürliche Zahlen ai (\(1 <= a_i <= 10^6\)) – die Anzahl der Personen in der i-Gruppe.
Die dritte Zeile enthält die Zahl q – Anzahl der Überfälle.
Im Folgenden werden die q Zeilen angegeben, die jeweils zwei Zahlen enthalten: li und ri (\(1 <= l_i <= r_i <= n\)) – die Nummern der Gruppen, die am i-Überfall teilnehmen.
Ausgabe
Geben Sie q von Zahlen aus, die jeweils in einer eigenen Zeile – auf die Aufgabe antworten.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6
1 3 7 1 4 100
3
1 3
3 4
2 6 |
21
7
8400 |