Statement is not available in English language
D. 12 725 9
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам надо придумать название для этой задачи. Для этого у вас есть массив $$$a$$$ из $$$n$$$ целых чисел. Названием должен быть отрезок из этого массива.

Чтобы вычислить лучшее название, вы решили выполнить $$$q$$$ запросов:

  • «l r»: вычислить красоту отрезка от $$$l$$$ до $$$r$$$, которая вычисляется по формуле: $$$\sum\limits_{l ≤ i≤ j ≤ r} a_i \cdot a_j$$$. То есть вам надо вычислить сумму по всем парам $$$a_i \cdot a_j$$$, по всем $$$l ≤ i≤ j ≤ r$$$. Поскольку значение может получится слишком большим, выведите его по модулю $$$10^9+7$$$.
Входные данные

Первая строка входных данных содержит два целых числа $$$n,q$$$ ($$$1 ≤ n, q ≤5 \cdot 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$0 ≤ a_i ≤ 10^9$$$).

Далее идут $$$q$$$ строк входных данных, которые содержат два числа массив — $$$l$$$ и $$$r$$$ ($$$1 ≤ l ≤ r ≤ n$$$), описание запросов.

Выходные данные

В каждой из $$$q$$$ строк выходных данных выведите одно целое число - ответ на запрос.

Система оценки
ГруппаБаллыДоп. ограниченияНеобх. группыКомментарий
$$$0$$$$$$0$$$——Тест из условия
$$$1$$$$$$39$$$$$$n, q \leq 500$$$——
$$$2$$$$$$23$$$$$$n, q \leq 3000$$$$$$1$$$—
$$$3$$$$$$15$$$$$$n \leq 3000$$$——
$$$4$$$$$$13$$$$$$l_i = 1$$$——
$$$6$$$$$$10$$$—$$$2, 3, 4$$$—
Пример
Входные данные
5 5
0 3 1 1 0
2 2
2 5
1 3
3 5
1 5
Выходные данные
9
18
13
3
18