Gangues de Fomin
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 terá exatamente um ladino de cada grupo cujo número está 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 nos cálculos e pede sua ajuda.
Entrada
A primeira linha é um 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 <= 2\) ) – número de pessoas no i-º 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úmeros de grupos que participaram do i-th raid.
Saída
Forneça números
q, cada um em uma linha separada – resposta à tarefa.
Exemplos
| # |
Entrada |
Saída |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |