Problem
La banda di Fomin è composta da n gruppi, ognuno dei quali ha unai persone. Sono pianificati raid q. Il i-esimo raid includerà esattamente un rapinatore 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.
Inserimento
La prima riga contiene il 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 < = 10^6\)) – il 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.
Impressum
Stampa i numeri
q, ciascuno su una riga separata – risposta al compito.
Esempi
| # |
Input |
Uscita |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |