Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Банды Фомина

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i_ом рейде будет участвовать ровно один  разбойник из каждой группы, номер которой лежит в отрезке [l_i, r_i]. 
Мелехов тоскует, поэтому для каждого рейда он решил посчитать кол-во возможных отрядов по модулю 10^9 + 7. Однако Григорий постоянно находиться в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные:
В первой строке дано число n (1 <= n <= 10^5) – кол-во групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (1 <= a_i <= 2) – кол-во человек в iой группе.
В третьей строке дано число q – кол-во рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (1 <= l_i <= r_i <= n) – номера групп, участвующих в iом рейде.

Выходные данные:
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Ввод Вывод
6
1 2 1 1 2 2
3
1 3
3 4
2 6
2
1
8

(с) Курбатов Е.
 
 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: