E. Числа на доске
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На доске написана последовательность из n целых чисел. Скоро к доске подойдёт Саша и начнёт делать следующую операцию: пусть x и y — два подряд идущих числа (x перед y), тогда он может их стереть и на их месте написать число x + 2y. Он делает такие операции, пока на доске не останется одно число. Саша очень любит большие числа и получит самое большое возможное число.

Никита хочет успеть к доске раньше Саши и стереть часть чисел. У него есть q вариантов, в варианте i он стирает все числа левее позиции li и все числа правее позиции ri, то есть на доске остаются все числа от li-го до ri-го включительно. Для каждого из вариантов ему интересно, какое число в итоге получится у Саши. Так как ответ может быть большим, выведите его по модулю 109 + 7.

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

В первой строке содержатся числа n и q (1 ≤ n, q ≤ 105) — количество чисел на доске и вариантов у Никиты, соответственно.

Следующая строка содержит n целых чисел a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — последовательность чисел на доске.

Следующие q строк содержат по два числа li и ri (1 ≤ li ≤ ri ≤ n), описывающие варианты Никиты.

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

Для каждого варианта Никиты выведите остаток от деления максимального числа, которое может получить Саша, на 109 + 7.

Примеры
Входные данные
3 3
1 2 3
1 3
1 2
2 3
Выходные данные
17
5
8
Входные данные
3 1
1 2 -3
1 3
Выходные данные
1000000006
Входные данные
4 2
1 1 1 -1
1 4
3 4
Выходные данные
5
1000000006
Примечание

Во втором примере Никита ничего не стирает. Саша первым действием сотрёт числа 1 и 2 и напишет 5. Потом он сотрёт 5 и -3 и получит -1. Остаток от деления -1 на 109 + 7 равен 109 + 6.