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 \in \{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 \le n, q \le 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 \le l_i \le r_i \le 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.

Difficulty: interview

Starter code:

Solutions:
import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def add(a,b):
	return (a+b)%1000000007

def mul(a,b):
	return (a*b)%1000000007

def sub(a,b):
	return (a-b+1000000007)%1000000007

def qpow(a, b):
	r = 1
	k = a
	for i in range(17):
		if b & (1<<i):
			r = mul(r, k)
		k = mul(k, k)
	return r

n, q = mints()
a = list(minp())
c = [0]*(n+1)
for i in range(n):
	c[i+1] = c[i] + int(a[i])
for i in range(q):
	l, r = mints()
	k = (r-l+1)
	o = c[r]-c[l-1]
	z = sub(qpow(2,o),1)
	print(mul(z,qpow(2,k-o)))

import sys
mod=10**9+7
n,q=list(map(int,sys.stdin.readline().split()))
S=sys.stdin.readline().strip()
LR=[list(map(int,sys.stdin.readline().split())) for i in range(q)]

LIST=[0]
for s in S:
    if s=="1":
        LIST.append(LIST[-1]+1)
    else:
        LIST.append(LIST[-1])

def count(m,n,mod):
    return (pow(2,m,mod)-1)*pow(2,n,mod)%mod

for l,r in LR:
    print(count(LIST[r]-LIST[l-1],r-l+1-LIST[r]+LIST[l-1],mod))
    


import sys
input_file = sys.stdin
C = (10**9+7)
[n, q] = list(int(i) for i in input_file.readline().split())
temp = input_file.readline()
lst = []
for char in temp[:-1]:
    lst.append(int(char))
    
new_lst = [(0, 0)]
for i in lst:
    if i == 0:
        new_lst.append((new_lst[-1][0]+1, new_lst[-1][1]))
    else:
        new_lst.append((new_lst[-1][0], new_lst[-1][1]+1))

ls = [1]
for i in range(n):
    ls.append(ls[-1]*2 % C)

for line in input_file:
    [l, r] = list(int(i) for i in line[:-1].split())
    q = (new_lst[r][0] - new_lst[l-1][0], new_lst[r][1] - new_lst[l-1][1])
    print((ls[sum(q)] - ls[q[0]]) % C)



# Causes TLE
# C++17 implemention -> 1062c.cpp

MOD = 1000000007

def main():
    buf = input()
    buflist = buf.split()
    n = int(buflist[0])
    q = int(buflist[1])
    buf = input()
    x = buf
    sum_list = [0] # sentinel / one indexing
    for i, deliciousness in enumerate(x):
        sum_list.append(int(deliciousness) + sum_list[i])
    enjoyment_list = [0]
    for i in range(n):
        enjoyment_list.append((enjoyment_list[i] * 2 + 1) % MOD)
    query_list = []
    for i in range(q):
        buf = input()
        buflist = buf.split()
        l = int(buflist[0]) # one indexing
        r = int(buflist[1]) # one indexing
        query_list.append((l, r))
    for i, query in enumerate(query_list):
        l = query[0]
        r = query[1]
        banhmi_count = r - l + 1
        delicious_count = sum_list[r] - sum_list[l - 1]
        non_delicious_count = banhmi_count - delicious_count
        enjoyment = 0
        # main part
        if delicious_count == 0:
            enjoyment = 0
        else:
            enjoyment += enjoyment_list[delicious_count]
            enjoyment += (enjoyment_list[banhmi_count] - enjoyment_list[delicious_count] - enjoyment_list[non_delicious_count])
            enjoyment = enjoyment % MOD
        print(enjoyment)

def __starting_point():
    main()

__starting_point()

n,q = list(map(int, input().split()))
a = input()
Q = []
for _ in range(q):
    Q.append(list(map(int, input().split())))
d = [0]
ab = 0
for i in a:
    if i == '1':
        ab += 1
    d.append(ab)
mod = int(1e9 + 7)
p = [1]
i = 1
for _ in range(n):
    i = (i*2)%mod
    p.append(i)
    
for l,r in Q:
    y = r-l + 1
    x = d[r] - d[l-1]
    y -= x
    print(((p[x]-1)*p[y])%mod)

import sys
input = sys.stdin.readline
out = sys.stdout
MOD = 1000000007

def main():
    n, q = list(map(int, input().split()))
    s = input()
    d = {}
    count_1 = 0
    count_0 = 0
    for i in range(n):
        if s[i] == '1':
            count_1 += 1
        else:
            count_0 += 1
        z = (count_1, count_0)
        d[i] = z
    for i in range(q):
        li, ri = list(map(int, input().split()))
        li -= 1
        ri -= 1
        if li == 0:
            answer = (pow(2, d[ri][0], MOD) - 1)*(pow(2, d[ri][1], MOD))
        else:
            answer = (pow(2, d[ri][0]-d[li-1][0], MOD) - 1)*(pow(2, d[ri][1]-d[li-1][1], MOD))
        out.write(str(answer % MOD) + '\n')
                      
def __starting_point():
    main()

__starting_point()

# 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)


def __starting_point():

    # 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)




__starting_point()

def beki(a,b):
    waru=10**9+7
    ans=1
    while(b>0):
        if(1 & b):
            ans= ans * a %waru
        b >>= 1
        a=a * a % waru
    return ans

n,m=map(int,input().split())
s=input()


ans=[]
waru=10**9+7
ruiseki=[0]*(n+1)
bekij=[1]*(n+1)
for i in range(n):
    ruiseki[i+1]=ruiseki[i]+int(s[i])
    bekij[i+1]=(bekij[i]*2)%waru
for i in range(m):
    l,r=map(int,input().split())
    ko=ruiseki[r]-ruiseki[l-1]
    ans.append(str((((bekij[ko] -1)) * ((bekij[r+1-l - ko]))) %waru))

print("\n".join(ans))

def beki(a,b):
    waru=10**9+7
    ans=1
    while(b>0):
        if(1 & b):
            ans= ans * a %waru
        b >>= 1
        a=a * a % waru
    return ans

n,m=map(int,input().split())
s=input()


ans=[]
waru=10**9+7
ruiseki=[0]*(n+1)
bekij=[1]*(n+1)
for i in range(n):
    ruiseki[i+1]=ruiseki[i]+int(s[i])
    bekij[i+1]=(bekij[i]*2)%waru
for i in range(m):
    l,r=map(int,input().split())
    ko=ruiseki[r]-ruiseki[l-1]
    ans.append((((bekij[ko] -1)) * ((bekij[r+1-l - ko]))) %waru)

print("\n".join(list(map(str,ans))))


import sys
def __starting_point():
    n, q = list(map(int, sys.stdin.readline().split()))
    arr = sys.stdin.readline()
    total = [0]*n
    if arr[0] == '1':
        total[0] = 1
    else:
        total[0] = 0
    for i in range(1, n):
        if arr[i] == '1':
            total[i] = total[i-1]+1
        else:
            total[i] = total[i-1]
    mod = 10**9+7
    for i in range(q):
        l, r = list(map(int, sys.stdin.readline().split()))
        l -= 1
        r -= 1
        length = r-l+1
        ans = pow(2, length, mod)
        ans = (ans-1+mod) % mod
        if l == 0:
            zeroes = length-total[r]
        else:
            zeroes = length-(total[r]-total[l-1])
        sub = pow(2, zeroes, mod)
        sub = (sub-1+mod) % mod
        ans = (ans-sub+mod) % mod
        print(ans)

__starting_point()

import sys
def numIN():
    return(map(int,sys.stdin.readline().strip().split()))

MOD = 10**9+7

n,q = numIN()
l = [int(i) for i in input()]
pre = []
s = 0
for i in l:
    s+=i
    pre.append(s)
for i in range(q):
    l,r = numIN()
    l-=1
    r-=1
    if l!=0:
        one = pre[r]-pre[l-1]
        zero = r-l+1-one
        x = pow(2,one,MOD)-1
        y = pow(2,zero,MOD)
        ans = x*y
        ans%=MOD
        print(ans)
    else:
        one = pre[r]
        zero = r-l+1-one
        x = pow(2,one,MOD)-1
        y = pow(2,zero,MOD)
        ans = x*y
        ans%=MOD
        print(ans)

from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
import sys
import math
MAX = sys.maxsize
MOD = 10**9+7
MAXN = 10**6+10
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b,x,y):
    return abs(a-x)+abs(b-y)

def numIN():
    return(map(int,sys.stdin.readline().strip().split()))

def charIN():
    return(sys.stdin.readline().strip().split())

def maxSubArraySum(a,size): 
      
    max_so_far = 0
    max_ending_here = 0
      
    for i in range(size): 
        max_ending_here = max_ending_here + a[i] 
        if max_ending_here < 0: 
            max_ending_here = 0 
        elif (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
              
    return max_so_far

def isPer(n):
	return((math.floor(n**0.5))==(math.ceil(n**0.5)))

def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
  
  
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
  
    return x

n,q = numIN()
l = [int(i) for i in input()]
pre = []
s = 0
for i in l:
	s+=i
	pre.append(s)
for i in range(q):
	l,r = numIN()
	l-=1
	r-=1
	if l!=0:
		one = pre[r]-pre[l-1]
		zero = r-l+1-one
		x = pow(2,one,MOD)-1
		y = pow(2,zero,MOD)
		ans = x*y
		ans%=MOD
		print(ans)
	else:
		one = pre[r]
		zero = r-l+1-one
		x = pow(2,one,MOD)-1
		y = pow(2,zero,MOD)
		ans = x*y
		ans%=MOD
		print(ans)

def beki(a,b):
    waru=10**9+7
    ans=1
    while(b>0):
        if(1 & b):
            ans= ans * a %waru
        b >>= 1
        a=a * a % waru
    return ans
n,m=list(map(int,input().split()))
s=input()

ans=[]
waru=10**9+7

ru=[0]*(n+1)
b=[1]*(n+1)
for i in range(n):
    ru[i+1]=ru[i]+int(s[i])
    b[i+1]=(b[i]*2)%waru
for i in range(m):
    l,r=list(map(int,input().split()))
    ko=ru[r]-ru[l-1]
    ans.append((((b[ko] -1)) * ((b[r+1-l - ko]))) %waru)

print("\n".join(list(map(str,ans))))