Fomins Bande
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 Bereich \([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 <= 2\)) – die Anzahl der Personen in der i--Gruppe.
In der dritten Zeile wird die Zahl q – Anzahl der Überfälle angegeben.
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 an i-ohm teilnehmen, sind i- und ri (\(1 <= l_i <= r_i <= n\)) überfall.
Ausgabe
Geben Sie
q von Zahlen aus, die jeweils in einer eigenen Zeile – auf die Aufgabe antworten.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |