A sequence of *n* integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let *x* and *y* be two adjacent numbers (*x* before *y*), then he can remove them and write *x* + 2*y* instead of them. He will perform these operations until one number is left. Sasha likes big numbers and will get the biggest possible number.

Nikita wants to get to the blackboard before Sasha and erase some of the numbers. He has *q* options, in the option *i* he erases all numbers to the left of the *l*<sub class="lower-index">*i*</sub>-th number and all numbers to the right of *r*<sub class="lower-index">*i*</sub>-th number, i. e. all numbers between the *l*<sub class="lower-index">*i*</sub>-th and the *r*<sub class="lower-index">*i*</sub>-th, inclusive, remain on the blackboard. For each of the options he wants to know how big Sasha's final number is going to be. This number can be very big, so output it modulo 10<sup class="upper-index">9</sup> + 7.
The first line contains two integers *n* and *q* (1 ≤ *n*, *q* ≤ 10<sup class="upper-index">5</sup>) — the number of integers on the blackboard and the number of Nikita's options.

The next line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> ( - 10<sup class="upper-index">9</sup> ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the sequence on the blackboard.

Each of the next *q* lines contains two integers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*), describing Nikita's options.
In the second sample Nikita doesn't erase anything. Sasha first erases the numbers 1 and 2 and writes 5. Then he erases 5 and -3 and gets -1. -1 modulo 10<sup class="upper-index">9</sup> + 7 is 10<sup class="upper-index">9</sup> + 6.
from random import randint


def find_max_ind(arr):
    max_el, max_ind = arr[0], 0
    for i in range(1, len(arr)):
        el = arr[i]
        if el >= max_el:
            max_el = el
            max_ind = i
    return max_ind

def calc_max_prod(arr, l):
    if l == 1:
        return arr[0]
    if l == 2:
        a = arr[0] + arr[1] * 2
        return a
    max_ind = find_max_ind(arr)
    if max_ind == 0:
        a = calc_max_prod([calc_max_prod(arr[:2], 2)] + arr[2:], l - 1)
        return a
    before = arr[:max_ind - 1]
    calc = arr[max_ind - 1:max_ind + 1]
    after = arr[max_ind + 1:]
    a = calc_max_prod(before + [calc_max_prod(calc, 2)] + after, l - 1)
    return a % (10 ** 9 + 7)



def calc_max_prod1(arr, l):
    if l == 1:
        return arr[0]
    if l == 2:
        return arr[0] + arr[1] * 2
    max_prod = -float("inf")
    for i in range(l - 1):
        prod = calc_max_prod(arr[:i] + [calc_max_prod(arr[i:i + 2], 2)] + arr[i + 2:], l - 1)
        max_prod = max(prod, max_prod)
    return max_prod % (10 ** 9 + 7)


def gen_test():
    n, q = randint(1, 5), randint(1, 10)
    arr1 = []
    for i in range(n):
        arr1.append(randint(1, 100))
    lri = []
    for i in range(q):
        li = randint(1, n - 2)
        ri = randint(li + 1, n)
        lri.append([li, ri])
    test = [[n, q], arr1, lri]
    return test

def test(number_tests):
    for i in range(number_tests):
        test = gen_test()
        n, q = test[0]
        arr = test[1]
        lri = test[2]
        for l in lri:
            li, ri = l
            res1 = calc_max_prod(arr[li - 1:ri], ri - li + 1)
            res2 = calc_max_prod1(arr[li - 1:ri], ri - li + 1)
            if res1 != res2:
                print("Incorretc answer!!!")
                print("Test:")
                print(n, q)
                print(arr)
                print(li, ri)
                print("First answer: ")
                print(res1)
                print("Correct answer: ")
                print(res2)

def targ():
    n, q = list(map(int, input().split()))
    nums = list(map(int, input().split()))
    rem = [list(map(int, input().split())) for i in range(q)]
    for i in range(q):
        li, ri = rem[i]
        print(calc_max_prod1(nums[li - 1:ri], ri - li + 1))


DEBUG = False
NUMBER_TESTS = 10
if DEBUG:
    test(NUMBER_TESTS)
else:
    targ()