Bande di Fomin
Problem
La banda di Fomin è composta da n gruppi, ognuno dei quali ha ai persone. Sono pianificati raid q. Il iesimo raid avrà esattamente un ladro per ogni gruppo il cui numero si trova nel segmento \([l_i, r_i]\). ;
Melekhov è triste, quindi per ogni raid ha deciso di calcolare il numero di unità possibili modulo
\(10^9 + 7\). Tuttavia, Gregory pensa costantemente al significato della vita e alla ricerca della verità, quindi non può concentrarsi sui calcoli e ti chiede aiuto.
Input
La prima riga è un numero n (\(1 <= n <= 10^5\)) – il numero di gruppi nella banda di Fomin.
La seconda riga contiene n numeri naturali ai (\(1 <= a_i <= 2\) ) – numero di persone nel i-esimo gruppo.
La terza riga contiene il numero q – numero di raid.
Le seguenti sono righe q, ciascuna contenente due numeri – li e ri (\(1 <= l_i <= r_i <= n\)) – numero di gruppi che partecipano al i-esimo raid.
Uscita
Produci i numeri
q, ciascuno su una riga separata – risposta al compito.
Esempi
| # |
Input |
Uscita |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |