Problem
Fomin's gang consists of n groups, each of which has ai people. q raids are planned. The i-th raid will include exactly one robber from each group whose number lies in the segment \([l_i, r_i]\).
Melekhov is sad, so for each raid he decided to calculate the number of possible units modulo
\(10^9 + 7\). However, Gregory is constantly thinking about the meaning of life and searching for the truth, so he cannot concentrate on calculations and asks you for help.
Input
The first line contains the number
n (
\(1 <= n <= 10^5\)) – the number of groups in Fomin's gang.
The second line contains
n natural numbers
ai (
\(1 <= a_i < = 10^6\)) – the number of people in the
i-th group.
The third line contains the number
q – number of raids.
The following are
q lines, each containing two numbers –
li and
ri (
\(1 <= l_i <= r_i <= n\)) – numbers of groups participating in
i-th raid.
Imprint
Print
q numbers, each on a separate line – response to the task.
Examples
| # |
Input |
Output |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |