Fomin's gang consists of n groups, each of which has ai people. q raids are planned. The ith raid will have exactly one rogue 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 is a 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 <= 2\) ) – number of people in 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 the i-th raid.
Output
Output
q numbers, each on a separate line – response to the task.
Examples
| # |
Input |
Output |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |