Задача . Банды Фомина №2

Банда Фомина состоит из 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