Банда Фомина состоит из n
групп, в каждой из которых ai
человек. Планируется провести q
рейдов. В i
-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).
Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю
\(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.
Входные данные
В первой строке дано число
n
(
\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано
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
3 4
2 6 |
21
7
8400 |