Problem
A gangue de Fomin consiste em n grupos, cada um com ai pessoas. Os ataques q estão planejados. A i-ésima invasão incluirá exatamente um robber de cada grupo cujo número esteja no segmento \([l_i, r_i]\).
Melekhov está triste, então para cada ataque ele decidiu calcular o número de unidades possíveis modulo
\(10^9 + 7\). No entanto, Gregory está constantemente pensando no sentido da vida e em busca da verdade, então ele não consegue se concentrar em cálculos e pede ajuda a você.
Entrada
A primeira linha contém o número
n (
\(1 <= n <= 10^5\)) – o número de grupos na gangue de Fomin.
A segunda linha contém
n números naturais
ai (
\(1 <= a_i < = 10^6\)) – o número de pessoas no
i-ésimo grupo.
A terceira linha contém o número
q – número de ataques.
A seguir estão as linhas
q, cada uma contendo dois números –
li e
ri (
\(1 <= l_i <= r_i <= n\)) – número de grupos participantes do
i-th raid.
Impressão
Imprima os números
q, cada um em uma linha separada – resposta à tarefa.
Exemplos
| # |
Entrada |
Saída |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |