На доске написана последовательность из n целых чисел. Скоро к доске подойдёт Саша и начнёт делать следующую операцию: пусть x и y — два подряд идущих числа (x перед y), тогда он может их стереть и на их месте написать число x + 2y. Он делает такие операции, пока на доске не останется одно число. Саша очень любит большие числа и получит самое большое возможное число.
Никита хочет успеть к доске раньше Саши и стереть часть чисел. У него есть q вариантов, в варианте i он стирает все числа левее позиции li и все числа правее позиции ri, то есть на доске остаются все числа от li-го до ri-го включительно. Для каждого из вариантов ему интересно, какое число в итоге получится у Саши. Так как ответ может быть большим, выведите его по модулю 109 + 7.
Выходные данные
Для каждого варианта Никиты выведите остаток от деления максимального числа, которое может получить Саша, на 109 + 7.
Примечание
Во втором примере Никита ничего не стирает. Саша первым действием сотрёт числа 1 и 2 и напишет 5. Потом он сотрёт 5 и -3 и получит -1. Остаток от деления -1 на 109 + 7 равен 109 + 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2 3
1 3
1 2
2 3
|
17
5
8
|
|
2
|
3 1
1 2 -3
1 3
|
1000000006
|
|
3
|
4 2
1 1 1 -1
1 4
3 4
|
5
1000000006
|