Problem
Fomin의 갱단은 n개의 그룹으로 구성되어 있으며 각 그룹에는 i 명이 있습니다. q 습격이 예정되어 있습니다. i번째 습격에는 각 그룹에서 정확히 한 명의 강도가 포함되며 그 번호는 \([l_i, r_i]\).
Melekhov는 슬프기 때문에 각 습격에 대해
\(10^9 + 7\) 모듈로 가능한 단위 수를 계산하기로 결정했습니다. 하지만 그레고리는 삶의 의미에 대해 끊임없이 고민하고 진실을 찾고 있기 때문에 계산에 집중하지 못하고 당신에게 도움을 요청합니다.
입력
첫 번째 줄에는 숫자
n(
\(1 <= n <= 10^5\)) – Fomin의 갱단의 수.
두 번째 줄에는
n개의 자연수
ai(
\(1 <= a_i < = 10^6\)) –
i번째 그룹의 사람 수.
세 번째 줄에는 숫자
q – 습격 횟수.
다음은 각각 두 개의 숫자를 포함하는
q 줄입니다.
li 및
ri (
\(1 <= l_i <= r_i <= n\)) –
i-번째 습격에 참여하는 그룹 수.
출판물
q개의 숫자를 각각 별도의 줄에 인쇄 – 작업에 대한 응답.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |