Problem: JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.

First, he splits the Banh-mi into n parts, places them on a row and numbers them from 1 through n. For each part i, he defines the deliciousness of the part as x_i ∈ \{0, 1\}. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the i-th part then his enjoyment of the Banh-mi will increase by x_i and the deliciousness of all the remaining parts will also increase by x_i. The initial enjoyment of JATC is equal to 0.

For example, suppose the deliciousness of 3 parts are [0, 1, 0]. If JATC eats the second part then his enjoyment will become 1 and the deliciousness of remaining parts will become [1, \\_, 1]. Next, if he eats the first part then his enjoyment will become 2 and the remaining parts will become [\\_, \\_, 2]. After eating the last part, JATC's enjoyment will become 4.

However, JATC doesn't want to eat all the parts but to save some for later. He gives you q queries, each of them consisting of two integers l_i and r_i. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range [l_i, r_i] in some order.

All the queries are independent of each other. Since the answer to the query could be very large, print it modulo 10^9+7.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 100 000).

The second line contains a string of n characters, each character is either '0' or '1'. The i-th character defines the deliciousness of the i-th part.

Each of the following q lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the segment of the corresponding query.

Output

Print q lines, where i-th of them contains a single integer — the answer to the i-th query modulo 10^9 + 7.

Examples

Input

4 2
1011
1 4
3 4


Output

14
3


Input

3 2
111
1 2
3 3


Output

3
1

Note

In the first example: 

  * For query 1: One of the best ways for JATC to eats those parts is in this order: 1, 4, 3, 2. 
  * For query 2: Both 3, 4 and 4, 3 ordering give the same answer. 



In the second example, any order of eating parts leads to the same answer.

Solution (in PYTHON3):

Solution:
# use this as the main template for python problems
import sys
from collections import Counter
NUM = int(1e9+7)

def compute1(size, tots):

    val = 0
    ans = 0
    for i in range(tots):
        delic = val + 1
        ans += delic
        val = ((val % NUM) + (delic % NUM)) % NUM
   
    print('=--') 
    for i in range(size - tots):
        delic = val
        ans += delic
        val = ((val % NUM) + (delic % NUM)) % NUM
        print(delic)
    print('=--') 
    return ans % int(1e9+7)


def compute2(size, tots):
#    ans = 2 ** tots - 1
    ans = power(2, tots, NUM) - 1
    ans = ((ans % NUM) * (power(2, (size - tots), NUM))) % NUM
    #ans = ((ans % NUM) * (2 ** (size - tots)) % NUM) % NUM
    return ans 

def power(x, y, p) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
          
    return res 

def solution(n, q, arr):

    st = SegmentTree(arr, '+')
    for x in range(q):
        l, r = [int(val) for val in sys.stdin.readline().split()]
        l -= 1
        r -= 1
        size = r - l + 1
        #tots = sum(arr[l:r+1])
        tots = st.query(l, r)
        print(compute2(size, tots))


def validate():
    from random import randint
    for i in range(1, 20000):
       
        tots = randint(0, i)
        val1 = compute1(i, tots)
        val2 = compute2(i, tots)
        if(val1 != val2):
            print(val1, val2)
            raise Exception()
    #print(compute(1000000, 1000000))


def random_query(n):
    from random import randint
    l = randint(0, n-1)
    r = randint(0, n-1)
    while(r < l):
        r = randint(0, n-1)
    return l, r

def random_sequence(n):
    from random import randint
    return [randint(0, 1) for val in range(n)]

class SegmentTree(object):
    
    # this class was constructed with inspiration and guidance from:
    # https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/
    # O(n) leaves, O(n-1) internal nodes.
    # build:  O(n) :D
    # update: O(k), where k = height of tree :D
    # query:  O(k), where k = height of tree :D
    
    def __init__(self, data, op):
        
        from math import log
        from math import ceil
        
        # The node of the tree is at index 0, thus tree[0] is the root
        # The children of three[i] are tored at tree[2*i+1] and tree[2*i+2]
        # The internal nodes in 
        
        self.n = len(data)
        self.tree = [0] * self.n*4 #int(2 * 2 ** (ceil(log(n, 2))) - 1) * 2
        self.merge_op = op
       
        self._build_tree(data, 0, 0, self.n-1)
 
    def _build_tree(self, data, ind, lo, hi):
        
        # call as build_tree(data, 0, 0, n-1)
    
        # leaf node, store value
        if (lo == hi):
            self.tree[ind] = data[lo]
            return
        
        # recurse
        mid = lo + (hi - lo) // 2
        self._build_tree(data, 2 * ind + 1, lo, mid)
        self._build_tree(data, 2 * ind + 2, mid + 1, hi)
    
        # merge
        self.tree[ind] = self._merge(self.tree[2 * ind + 1], self.tree[2 * ind + 2])
        
    def _merge(self, val1, val2):
        
        if(self.merge_op == '+'):
            return val1 + val2
        elif(self.merge_op == "OR"):
            return val1 | val2
        elif(self.merge_op == "XOR"):
            return val1 ^ val2
        elif(self.merge_op == "*"):
            return val1 * val2 
 
    def query(self, i, j, ind=0, lo=0, hi=None):
    #def query(self, ind, lo, hi, i, j):
        # call as query(0, 0, n-1, i, j)
        # where i:j is the slice being queried
        if(hi == None):
            hi = self.n-1        

        if (lo > j or hi < i):
            raise Exception()
            return 0 # represents null node completely outside segment
        
        if (i <= lo and j >= hi):
            return self.tree[ind]
        
        mid = lo + (hi - lo) // 2
        
        if (i > mid):
            return self.query(i, j, 2 * ind + 2, mid + 1, hi)
        elif (j <= mid):
            return self.query(i, j, 2 * ind + 1, lo, mid)
        
        lq = self.query(i, mid, 2 * ind + 1, lo, mid)
        rq = self.query(mid + 1, j, 2 * ind + 2, mid + 1, hi)
    
        return self._merge(lq, rq)


if __name__ == "__main__":

    # single variables
    n, q = [int(val) for val in sys.stdin.readline().split()]

    # vectors
    arr = [int(val) for val in sys.stdin.readline().split()[0]]

    #validate()
    # solve it!
    solution(n, q, arr)