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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation

Greedy algorithms


Solutions:
import sys
r = sys.stdin.readlines()
M = 10 ** 9 + 7
(n, q) = r[0].strip().split()
n = int(n)
q = int(q)
s = r[1]
p = [0]
k = 0
for v in range(n):
	d = int(s[v])
	k += 1 - d
	p.append(k)
for k in range(q):
	(a, b) = r[k + 2].strip().split()
	a = int(a)
	b = int(b)
	l = b - a + 1
	zero = p[b] - p[a - 1]
	sys.stdout.write(str((pow(2, l, M) - pow(2, zero, M) + M) % M))
	sys.stdout.write('\n')


from sys import *
m = 1000000007
(n, q) = map(int, stdin.readline().split())
a = stdin.readline()
ans = []
t = []
count = 0
for i in a:
	if i == '1':
		count += 1
	t.append(count)
for _ in range(q):
	(x, y) = map(int, input().split())
	if x == 1:
		p = t[y - 1]
	else:
		p = t[y - 1] - t[x - 2]
	q = y - x + 1 - p
	s = pow(2, p + q, m) % m
	s = s % m - pow(2, q, m) % m
	ans.append(s % m)
stdout.write('\n'.join(map(str, ans)))


(N, M) = map(int, input().split())
A = [int(x) for x in input()]
memo = [-1] * (N + 1)

def pow(n):
	if n == 0:
		return 1
	if n < 30:
		return 1 << n
	if memo[n] >= 0:
		return memo[n]
	half = pow(n // 2)
	ans = half * half
	if n % 2 != 0:
		ans *= 2
	ans %= MOD
	memo[n] = ans
	return ans
MOD = 10 ** 9 + 7
left = [0] * (N + 1)
for i in range(1, N + 1):
	left[i] = left[i - 1] + A[i - 1]
ans = []
for qi in range(M):
	(l, r) = map(int, input().split())
	ones = left[r] - left[l - 1]
	zeros = r - l + 1 - ones
	x = pow(ones) - 1
	y = x * (pow(zeros) - 1)
	ans.append((x + y) % MOD)
print('\n'.join(map(str, 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))))


import sys
r = sys.stdin.readlines()
(n, q) = r[0].split(' ')
n = int(n)
q = int(q)
M = 10 ** 9 + 7
twopow = [1] * (2 * n + 1)
for j in range(1, 2 * n + 1):
	twopow[j] = twopow[j - 1] * 2 % M
s = r[1]
p = [0] * (n + 1)
for v in range(n):
	p[v + 1] = p[v] + (s[v] == '1')
ans = [0] * q
for k in range(q):
	(a, b) = r[k + 2].split(' ')
	a = int(a)
	b = int(b)
	l = b - a + 1
	one = p[b] - p[a - 1]
	v = (twopow[l] - twopow[l - one] + M) % M
	ans[k] = str(v)
sys.stdout.write('\n'.join(ans))


import sys
(n, q) = 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) = 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)


def init_input():
	import os
	from sys import stdin
	it = iter(os.read(stdin.fileno(), 10 ** 7).split())
	return (lambda : next(it).decode(), lambda : int(next(it)), lambda : float(next(it)))
(ns, ni, nf) = init_input()
MOD = 10 ** 9 + 7
(n, q) = (ni(), ni())
s = 'x' + ns()
c = [0] * (n + 1)
for i in range(1, n + 1):
	c[i] = c[i - 1] + (s[i] == '1')
p2 = [1] * (2 * n + 1)
for i in range(1, 2 * n + 1):
	p2[i] = p2[i - 1] * 2 % MOD
out = []
for qq in range(q):
	(l, r) = (ni(), ni())
	o = c[r] - c[l - 1]
	z = r - l + 1 - o
	ans = (p2[o + z] - 1 - p2[z] + 1) % MOD
	out.append(ans)
print(*out, sep='\n')


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
MOD = 10 ** 9 + 7
l = list(input())
acc = [0]
for li in l:
	acc.append(acc[-1] + (1 if li == '1' else 0))
for _ in range(q):
	(l, r) = map(int, input().split())
	a = acc[r] - acc[l - 1]
	b = r - l + 1 - a
	print(pow(2, b, MOD) * (pow(2, a, MOD) - 1) % MOD)


import sys
input = sys.stdin.readline
(n, q) = list(map(int, input().split()))
s = list(input())
a = [0]
b = 0
for i in range(n):
	b = b + int(s[i])
	a.append(b)
mod = 10 ** 9 + 7
for i in range(q):
	(b, c) = list(map(int, input().split()))
	d = a[c] - a[b - 1]
	e = c - b + 1 - d
	f = (pow(2, d, mod) - 1) * pow(2, e, mod)
	print(f % mod)


from sys import *
mod = int(1000000000.0 + 7)
sum0 = [0] * 100005
sum1 = [0] * 100005
f = [0] * 100005
f[1] = 1
res = 1
for i in range(2, 100001):
	res = res * 2 % mod
	f[i] = (f[i - 1] + res) % mod
(n, q) = map(int, stdin.readline().split())
s = stdin.readline()
for i in range(len(s)):
	sum0[i + 1] = sum0[i]
	sum1[i + 1] = sum1[i]
	if s[i] == '1':
		sum1[i + 1] += 1
	else:
		sum0[i + 1] += 1
for i in range(q):
	(l, r) = map(int, stdin.readline().split())
	one = sum1[r] - sum1[l - 1]
	zero = sum0[r] - sum0[l - 1]
	ans = f[one]
	ans += f[one] * f[zero]
	ans %= mod
	print(ans)


(n, q) = map(int, input().split())
arr = input()
cumulative = [0]
num_ones = 0
for i in range(n):
	if arr[i] == '1':
		num_ones += 1
	cumulative.append(num_ones)
mod = 10 ** 9 + 7
res = []
for i in range(q):
	(a, b) = map(int, input().split())
	ones = cumulative[b] - cumulative[a - 1]
	zeros = b - a + 1 - ones
	res.append((pow(2, ones, mod) - 1) * pow(2, zeros, mod) % mod)
print('\n'.join(map(str, res)))


import sys
import math
input = sys.stdin.readline
(n, q) = map(int, input().split())
s = input()
zero = []
one = []
cz = 0
c1 = 0
for i in range(n):
	if s[i] == '0':
		cz += 1
		zero.append(cz)
		one.append(c1)
	else:
		c1 += 1
		zero.append(cz)
		one.append(c1)
one = [0] + one
zero = [0] + zero
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	p = one[r] - one[l]
	sum = pow(2, p, 10 ** 9 + 7) - 1
	z = zero[r] - zero[l]
	a = sum * (pow(2, z, 10 ** 9 + 7) - 1)
	print((sum + a) % (10 ** 9 + 7))


MOD = 1000000007

def main():
	buf = input()
	buflist = buf.split()
	n = int(buflist[0])
	q = int(buflist[1])
	buf = input()
	x = buf
	sum_list = [0]
	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])
		r = int(buflist[1])
		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
		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)
main()


import sys
r = sys.stdin.readlines()
M = 10 ** 9 + 7
(n, q) = r[0].split(' ')
n = int(n)
q = int(q)
s = r[1]
p = [0]
for v in range(n):
	p.append(p[v] + int(s[v]))
ans = []
for k in range(q):
	(a, b) = r[k + 2].split(' ')
	a = int(a)
	b = int(b)
	l = b - a + 1
	one = p[b] - p[a - 1]
	v = (pow(2, l, M) - pow(2, l - one, M) + M) % M
	ans.append(str(v))
	ans.append('\n')
sys.stdout.writelines(ans)


from sys import stdin, stdout
import cProfile, math
from collections import Counter
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10000000)

class Operation:

	def __init__(self, name, function, function_on_equal, neutral_value=0):
		self.name = name
		self.f = function
		self.f_on_equal = function_on_equal

def add_multiple(x, count):
	return x * count

def min_multiple(x, count):
	return x

def max_multiple(x, count):
	return x
sum_operation = Operation('sum', sum, add_multiple, 0)
min_operation = Operation('min', min, min_multiple, 1000000000.0)
max_operation = Operation('max', max, max_multiple, -1000000000.0)

class SegmentTree:

	def __init__(self, array, operations=[sum_operation, min_operation, max_operation]):
		self.array = array
		if type(operations) != list:
			raise TypeError('operations must be a list')
		self.operations = {}
		for op in operations:
			self.operations[op.name] = op
		self.root = SegmentTreeNode(0, len(array) - 1, self)

	def query(self, start, end, operation_name):
		if self.operations.get(operation_name) == None:
			raise Exception('This operation is not available')
		return self.root._query(start, end, self.operations[operation_name])

	def summary(self):
		return self.root.values

	def update(self, position, value):
		self.root._update(position, value)

	def update_range(self, start, end, value):
		self.root._update_range(start, end, value)

	def __repr__(self):
		return self.root.__repr__()

class SegmentTreeNode:

	def __init__(self, start, end, segment_tree):
		self.range = (start, end)
		self.parent_tree = segment_tree
		self.range_value = None
		self.values = {}
		self.left = None
		self.right = None
		if start == end:
			self._sync()
			return
		self.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)
		self.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)
		self._sync()

	def _query(self, start, end, operation):
		if end < self.range[0] or start > self.range[1]:
			return None
		if start <= self.range[0] and self.range[1] <= end:
			return self.values[operation.name]
		self._push()
		left_res = self.left._query(start, end, operation) if self.left else None
		right_res = self.right._query(start, end, operation) if self.right else None
		if left_res is None:
			return right_res
		if right_res is None:
			return left_res
		return operation.f([left_res, right_res])

	def _update(self, position, value):
		if position < self.range[0] or position > self.range[1]:
			return
		if position == self.range[0] and self.range[1] == position:
			self.parent_tree.array[position] = value
			self._sync()
			return
		self._push()
		self.left._update(position, value)
		self.right._update(position, value)
		self._sync()

	def _update_range(self, start, end, value):
		if end < self.range[0] or start > self.range[1]:
			return
		if start <= self.range[0] and self.range[1] <= end:
			self.range_value = value
			self._sync()
			return
		self._push()
		self.left._update_range(start, end, value)
		self.right._update_range(start, end, value)
		self._sync()

	def _sync(self):
		if self.range[0] == self.range[1]:
			for op in self.parent_tree.operations.values():
				current_value = self.parent_tree.array[self.range[0]]
				if self.range_value is not None:
					current_value = self.range_value
				self.values[op.name] = op.f([current_value])
		else:
			for op in self.parent_tree.operations.values():
				result = op.f([self.left.values[op.name], self.right.values[op.name]])
				if self.range_value is not None:
					bound_length = self.range[1] - self.range[0] + 1
					result = op.f_on_equal(self.range_value, bound_length)
				self.values[op.name] = result

	def _push(self):
		if self.range_value is None:
			return
		if self.left:
			self.left.range_value = self.range_value
			self.right.range_value = self.range_value
			self.left._sync()
			self.right._sync()
			self.range_value = None

	def __repr__(self):
		ans = '({}, {}): {}\n'.format(self.range[0], self.range[1], self.values)
		if self.left:
			ans += self.left.__repr__()
		if self.right:
			ans += self.right.__repr__()
		return ans

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def primeFactors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def isprime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def test_print(*args):
	if test:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result
TestCases = False
test = False

def main():
	(n, q) = get_tuple()
	li = list(map(int, list(input())))
	ones = [0]
	k = 0
	for i in li:
		k += i
		ones.append(k)
	for i in range(q):
		(l, r) = get_tuple()
		sm = ones[r] - ones[l - 1]
		print((pow(2, sm, P) - 1) * pow(2, r - l + 1 - sm, P) % P)
if TestCases:
	for _ in range(get_int()):
		cProfile.run('main()') if test else main()
else:
	cProfile.run('main()') if test else main()


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 5)
from queue import PriorityQueue
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
(n, q) = map(int, input().split())
l = list(input())
pref = [0]
for i in l:
	pref.append(pref[-1] + int(i))
for i in range(q):
	(a, b) = map(int, input().split())
	z = pref[b] - pref[a - 1]
	k1 = pow(2, z, mod) - 1
	z1 = b - a + 1 - z
	k2 = k1 % mod * (pow(2, z1, mod) - 1)
	k2 %= mod
	print((k1 + k2) % mod)


import math
import sys
from collections import defaultdict, Counter, deque, OrderedDict
import bisect
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]
from itertools import accumulate, groupby
import sys
M = 1000000000 + 7

def fast_exp(bas, exp):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % M
		bas = bas * bas % M
		exp = exp // 2
	return t % M

def fun(x, y):
	a = fast_exp(2, y) - 1
	b = fast_exp(2, x)
	return a * b % M
(n, q) = ilele()
S = input()
pre = [(0, 0)]
zeroes = 0
ones = 0
for i in S:
	if i == '1':
		ones += 1
	else:
		zeroes += 1
	pre.append((zeroes, ones))
for i in range(q):
	(l, r) = ilele()
	x = pre[l - 1]
	y = pre[r]
	z = y[0] - x[0]
	o = y[1] - x[1]
	print(fun(z, o))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a // gcd(a, b) * b

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
s = list(input())
s = s[:-1]
nn = 1000000007
N = 1000003
l = [0] * N
ll = [0] * (n + 1)
tt = 0
for i in range(n):
	if s[i] == 48:
		tt += 1
	ll[i + 1] = tt
temp = 1
for i in range(N):
	l[i] = temp % nn
	temp = temp + temp
	temp = temp % nn
for i in range(q):
	(a, b) = map(int, input().split())
	d = ll[b] - ll[a - 1]
	c = b - a + 1 - d
	e = l[c] - 1
	f = l[d]
	print(e * f % nn)


(n, q) = map(int, input().split())
a = list(map(int, list(input())))
p = [0] + a[:]
M = 10 ** 9 + 7
for i in range(1, n + 1):
	p[i] += p[i - 1]
o = []
for _ in range(q):
	(l, r) = map(int, input().split())
	w = p[r] - p[l - 1]
	z = r - l + 1 - w
	o.append(str((pow(2, w + z, M) - pow(2, z, M)) % M))
print('\n'.join(map(str, o)))


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

def main():
	(n, q) = 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) = 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')
main()


import itertools as it
import sys
MOD = 10 ** 9 + 7
(n, q) = map(int, next(sys.stdin).split())
s = [0] + list(it.accumulate(map(int, next(sys.stdin).strip())))
pow2 = [1]
for _ in range(1, n + 1):
	pow2.append((pow2[-1] << 1) % MOD)
ans = []
for _ in range(q):
	(l, r) = map(int, next(sys.stdin).split())
	ones = s[r] - s[l - 1]
	ans.append(str(pow2[r - l - ones + 1] * (pow2[ones] - 1) % MOD))
print('\n'.join(ans))


from sys import stdin, stdout
import collections
(N, Q) = [int(x) for x in stdin.readline().split()]
s = input()
ones = [0] * N
t = 0
for i in range(N):
	if s[i] == '1':
		t += 1
	ones[i] = t
find = [1] * (N + 1)
for i in range(1, N + 1):
	find[i] = find[i - 1] * 2 % 1000000007
ans = [0] * Q
for i in range(Q):
	(L, R) = [int(x) for x in stdin.readline().split()]
	L -= 1
	R -= 1
	if L == 0:
		one = ones[R]
	else:
		one = ones[R] - ones[L - 1]
	if one == 0:
		ans[i] = 0
	else:
		size = R - L + 1
		a1 = find[size - 1]
		res = find[size] - find[size - one]
		ans[i] = res % 1000000007
print(*ans, sep='\n')


import sys
r = sys.stdin.readlines()
M = 10 ** 9 + 7
(n, q) = map(int, r[0].strip().split())
s = list(map(int, r[1].strip()))
p = [0]
for i in range(n):
	p.append(p[i] + int(s[i]))
ans = []
for k in range(q):
	(a, b) = map(int, r[k + 2].strip().split())
	l = b - a + 1
	one = p[b] - p[a - 1]
	zero = l - one
	ans.append(str((pow(2, one, M) - 1) * pow(2, zero, M) % M))
sys.stdout.write('\n'.join(ans))


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
s = input()
pref = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	pref[i] = pref[i - 1] + (s[i - 1] == '1')
mod = 1000000007
ans = []
for i in range(q):
	(a, b) = map(int, input().split())
	k = pref[b] - pref[a - 1]
	N = b - a + 1
	z = N - k
	ans.append((pow(2, k, mod) - 1) * pow(2, z, mod) % mod)
print(*ans)


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
from collections import Counter
NUM = int(1000000000.0 + 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(1000000000.0 + 7)

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

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		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 = 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()

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

	def __init__(self, data, op):
		from math import log
		from math import ceil
		self.n = len(data)
		self.tree = [0] * self.n * 4
		self.merge_op = op
		self._build_tree(data, 0, 0, self.n - 1)

	def _build_tree(self, data, ind, lo, hi):
		if lo == hi:
			self.tree[ind] = data[lo]
			return
		mid = lo + (hi - lo) // 2
		self._build_tree(data, 2 * ind + 1, lo, mid)
		self._build_tree(data, 2 * ind + 2, mid + 1, hi)
		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):
		if hi == None:
			hi = self.n - 1
		if lo > j or hi < i:
			raise Exception()
			return 0
		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():
	(n, q) = [int(val) for val in sys.stdin.readline().split()]
	arr = [int(val) for val in sys.stdin.readline().split()[0]]
	solution(n, q, arr)
__starting_point()


import sys
mod = 10 ** 9 + 7
(n, q) = 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))


(n, q) = map(int, input().split())
st = input()
sum_st = [0]
add = 0
for i in st:
	if i == '1':
		add += 1
	sum_st.append(add)
count = 0
M = 10 ** 9 + 7
ans = []
for i in range(q):
	(l, r) = map(int, input().split())
	x = sum_st[r] - sum_st[l - 1]
	y = r - l - x + 1
	rs = (pow(2, x, M) - 1) % M
	ss = rs * pow(2, y, M) % M
	ans.append(ss)
for i in ans:
	print(i)


mod = 1000000007
(n, q) = list(map(int, input().split()))
arr = list(map(int, list(input())))
s = 0
preSum = []
for i in range(n):
	s += arr[i]
	preSum.append(s)
ans = []
for i in range(q):
	(l, r) = list(map(int, input().split()))
	am = r - l + 1
	s = preSum[r - 1] - preSum[l - 1] + arr[l - 1]
	perfect = pow(2, am, mod)
	minus = pow(2, am - s, mod)
	ans += [(perfect - minus + mod) % mod]
print(*ans, sep='\n')


import configparser
import math
import sys
input = sys.stdin.readline

def mod_exp(base, exp, mod):
	cur_iter = base
	cur_iter %= mod
	result = 1
	while exp > 0:
		if 1 & exp > 0:
			result = result * cur_iter
			result %= mod
		cur_iter *= cur_iter
		cur_iter %= mod
		exp = exp >> 1
	return result % mod

def mod_mul(a, b, mod):
	return a % mod * (b % mod) % mod

def mod_add(a, b, mod):
	return (a % mod + b % mod) % mod

def main():
	mod = int(1000000000.0) + 7
	(n, q) = [int(x) for x in input().split(' ')]
	s = input().strip()
	cnt0 = [0 for i in range(n)]
	cnt1 = [0 for i in range(n)]
	cnt0[0] = int(s[0] == '0')
	cnt1[0] = int(s[0] == '1')
	for i in range(1, n):
		cnt0[i] = (s[i] == '0') + cnt0[i - 1]
		cnt1[i] = (s[i] == '1') + cnt1[i - 1]
	for i in range(q):
		(l, r) = [int(x) for x in input().split(' ')]
		l -= 1
		r -= 1
		x = cnt0[r]
		if l != 0:
			x -= cnt0[l - 1]
		y = cnt1[r]
		if l != 0:
			y -= cnt1[l - 1]
		ans = mod_exp(2, y, mod) - 1
		if x > 0:
			ans += mod_mul(ans, mod_exp(2, x, mod) - 1, mod)
			ans %= mod
		print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 1000000007
(n, m) = map(int, input().split())
s = list(input())
l = [0] * (n + 1)
for i in range(1, n + 1):
	l[i] = l[i - 1] + int(s[i - 1])
for i in range(m):
	(l1, r) = map(int, input().split())
	s = r - l1
	no = l[r] - l[l1 - 1]
	ans = pow(2, s + 1, mod) - pow(2, s - no + 1, mod)
	print(ans % mod)


(n, q) = map(int, input().split())
delish = list(map(int, list(input())))
mod = 10 ** 9 + 7
sums = [0] + delish[:]
for i in range(n):
	sums[i + 1] += sums[i]
op = []
for _ in range(q):
	(l, r) = map(int, input().split())
	a = sums[r] - sums[l - 1]
	b = r - l + 1 - a
	op.append((pow(2, a + b, mod) - pow(2, b, mod)) % mod)
print('\n'.join(map(str, op)))


(n, q) = map(int, input().split())
a = input()
sums = []
degrees = [1, 2]
res = []
d = 2
if a[0] == '1':
	s = 1
else:
	s = 0
sums.append(s)
for i in range(1, n):
	if a[i] == '1':
		s += 1
	d = d * 2 % 1000000007
	sums.append(s)
	degrees.append(d)
for i in range(0, q):
	(l, r) = map(int, input().split())
	k0 = r - sums[r - 1] - (l - sums[l - 1])
	k1 = sums[r - 1] - sums[l - 1]
	if a[l - 1] == '0':
		k0 += 1
	else:
		k1 += 1
	R = degrees[k0] * (degrees[k1] - 1) % 1000000007
	res.append(R)
for i in range(0, q):
	print(res[i])


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	mod = 1000000007
	f = [1]
	t = [1]
	for i in range(1, 100005):
		t.append(t[-1] * 2 % mod)
		f.append((f[-1] + t[i]) % mod)
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, q) = ria()
		s = rs()
		cs1 = [0]
		cs0 = [0]
		ns1 = 0
		ns0 = 0
		for i in range(n):
			if s[i] == '1':
				ns1 += 1
			else:
				ns0 += 1
			cs1.append(ns1)
			cs0.append(ns0)
		for i in range(q):
			(l, r) = ria()
			n1q = cs1[r] - cs1[l - 1]
			n0q = cs0[r] - cs0[l - 1]
			ans = 0
			if n1q > 0:
				ans += f[n1q - 1]
			if n0q > 0:
				ans += (t[n1q] - 1) * f[n0q - 1]
			wi(ans % mod)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from sys import stdin, stdout

def BigMod(a, b, m):
	if b == 0:
		return 1 % m
	x = BigMod(int(a), int(b / 2), int(m))
	x = x * x % m
	if b % 2 == 1:
		return x * a % m
	return x
(n, m) = map(int, stdin.readline().split())
ch = stdin.readline()
base = [1 for i in range(n + 1)]
pw = [1 for i in range(n + 1)]
cum = [0 for i in range(n + 1)]
for i in range(n):
	cum[i + 1] = cum[i]
	if ch[i] == '1':
		cum[i + 1] += 1
Mod = int(1000000000.0 + 7)
pw[0] = int(1)
for i in range(1, n + 1):
	pw[i] = int(int(pw[i - 1] * 2) % Mod)
for i in range(1, n + 1):
	base[i] = (base[i - 1] % Mod + pw[i] % Mod) % Mod
while m > 0:
	(l, r) = map(int, stdin.readline().split())
	cur = cum[r] - cum[l - 1]
	m -= 1
	if cur == 0:
		stdout.write('0' + '\n')
		continue
	ans = int(base[cur - 1] % Mod * (pw[int(r - l + 1 - cur)] % Mod) % Mod)
	stdout.write(str(ans) + '\n')


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)


from sys import stdout, stdin
(n, q) = tuple(map(int, stdin.readline().split()))
s = stdin.readline()
mod = 1000000007
powers = [1 for i in range(n + 1)]
for i in range(1, n + 1):
	powers[i] = powers[i - 1] + powers[i - 1]
	if powers[i] >= mod:
		powers[i] -= mod
cum = [0 for i in range(n + 1)]
for i in range(n):
	if s[i] == '0':
		cum[i + 1] = cum[i] + 1
	else:
		cum[i + 1] = cum[i]
while q:
	(l, r) = tuple(map(int, stdin.readline().split(' ')))
	lent = r - l + 1
	zeroes = cum[r] - cum[l - 1]
	stdout.write(str(powers[zeroes] * (powers[lent - zeroes] - 1 + mod) % mod) + '\n')
	q -= 1


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
s = list(input().rstrip())
mod = 10 ** 9 + 7
for i in range(n):
	s[i] = int(s[i])
cnt = [0] * (n + 1)
for i in range(n):
	if s[i] == 1:
		cnt[i + 1] += 1
for i in range(1, n + 1):
	cnt[i] += cnt[i - 1]
p = [0] * (10 ** 6 + 1)
p[0] = 1
for i in range(1, 10 ** 6 + 1):
	p[i] = p[i - 1] * 2 % mod
for _ in range(q):
	(l, r) = map(int, input().split())
	cnt1 = cnt[r] - cnt[l - 1]
	cnt0 = r - l + 1 - cnt1
	ans = (p[cnt1] - 1 + (p[cnt1] - 1) * (p[cnt0] - 1)) % mod
	print(ans)


import sys
import io, os
input = sys.stdin.readline

def main():
	(n, q) = map(int, input().split())
	A = str(input().rstrip())
	A = [int(a) for a in A]
	from itertools import accumulate
	C = [0] + A
	C = list(accumulate(C))
	N = 10 ** 5 + 50
	mod = 10 ** 9 + 7
	table = [0] * N
	table[0] = 1
	for i in range(1, N):
		table[i] = table[i - 1] * 2
		table[i] %= mod
	for i in range(q):
		(l, r) = map(int, input().split())
		(l, r) = (l - 1, r - 1)
		c1 = C[r + 1] - C[l]
		c0 = r - l + 1 - c1
		ans = table[r - l + 1] - 1 - (table[c0] - 1)
		print(ans % mod)
main()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = [int(z) for z in input().rstrip()]
prefsums = [0, arr[0]]
for i in range(1, n):
	prefsums.append(prefsums[i] + arr[i])
for query in range(q):
	(l, r) = map(int, input().split())
	num1 = prefsums[r] - prefsums[l - 1]
	num0 = r - l + 1 - num1
	p1 = pow(2, num1, 10 ** 9 + 7) - 1
	p2 = (pow(2, num0, 10 ** 9 + 7) - 1) * p1 % (10 ** 9 + 7)
	sys.stdout.write(str((p1 + p2) % (10 ** 9 + 7)) + '\n')


import os
import sys
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(1):
	(n, q) = value()
	a = [int(i) for i in input()]
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] += pre[i] + a[i]
	for i in range(q):
		(l, r) = value()
		ones = pre[r] - pre[l - 1]
		tot = r - l + 1
		num = pow(2, tot - ones, M) * (pow(2, ones, M) - 1 + M) % M % M
		print(num)


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)


for _ in range(1):
	(n, q) = map(int, input().split())
	s = input()
	s = list(s)
	zeros = [0] * n
	ones = [0] * n
	if s[0] == '1':
		ones[0] = 1
	else:
		zeros[0] = 1
	for i in range(1, n):
		ones[i] += ones[i - 1]
		zeros[i] += zeros[i - 1]
		if s[i] == '1':
			ones[i] += 1
		else:
			zeros[i] += 1
	zeros = [0] + zeros
	ones = [0] + ones
	mod = 1000000007
	a = []
	for i in range(q):
		(l, r) = map(int, input().split())
		x = ones[r] - ones[l - 1]
		y = zeros[r] - zeros[l - 1]
		ans = (pow(2, x, mod) - 1) % mod
		ans = ans * pow(2, y, mod) % mod
		a.append(str(ans))
	print('\n'.join(map(str, a)))


from sys import stdin, stdout
MOD = 10 ** 9 + 7
(n, q) = list(map(int, stdin.readline().strip().split()))
s = list(map(int, list(stdin.readline().strip())))
cf = {0: 0}
for i in range(1, n + 1):
	cf[i] = cf[i - 1] + s[i - 1]
for _ in range(q):
	(l, r) = list(map(int, stdin.readline().strip().split()))
	cv = cf[r] - cf[l - 1]
	if cv:
		h = 0
		lenv = r - l + 1 - cv
		h += pow(2, cv, MOD) - 1
		h += (pow(2, lenv, MOD) - 1) * h % MOD
		h %= MOD
		stdout.write('{}\n'.format(h))
	else:
		stdout.write('0\n')


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return l

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(''.join([str(x) for x in a]) + '\n')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = 1
for _ in range(t):
	(n, q) = li()
	s = si()
	s = list(s)
	zeros = [0] * n
	ones = [0] * n
	if s[0] == '1':
		ones[0] = 1
	else:
		zeros[0] = 1
	for i in range(1, n):
		ones[i] += ones[i - 1]
		zeros[i] += zeros[i - 1]
		if s[i] == '1':
			ones[i] += 1
		else:
			zeros[i] += 1
	zeros = [0] + zeros
	ones = [0] + ones
	mod = 1000000007
	a = []
	for i in range(q):
		(l, r) = li()
		x = ones[r] - ones[l - 1]
		y = zeros[r] - zeros[l - 1]
		ans = (pow(2, x, mod) - 1) % mod
		ans = ans * pow(2, y, mod) % mod
		a.append(str(ans))
	print('\n'.join(map(str, a)))


from sys import stdin, stdout
(n, q) = tuple(map(int, stdin.readline().split()))
arr = list(str(stdin.readline()))[:-1]
arr[0] = int(arr[0])
for i in range(1, n):
	arr[i] = int(arr[i]) + arr[i - 1]
arr.insert(0, 0)
mod = int(1000000000.0 + 7)
inputs = [tuple(map(int, line.split())) for line in stdin]
ans = []
for (l, r) in inputs:
	o = arr[r] - arr[l - 1]
	z = r - l + 1 - o
	e_o = (pow(2, o, mod) - 1) % mod
	e_z = e_o * (pow(2, z, mod) - 1) % mod
	ans.append(str(int((e_o + e_z) % mod)))
stdout.write('\n'.join(ans))


from sys import stdin
input = stdin.readline

def power(a, b, mod):
	res = 1
	while b:
		if b % 2:
			res = res * a % mod
		b //= 2
		a = a * a % mod
	return res % mod
(n, q) = map(int, input().split())
s = list(map(int, input().strip()))
MOD = 10 ** 9 + 7
zeroes = [0] * (n + 1)
ones = [0] * (n + 1)
for i in range(1, 1 + n):
	zeroes[i] = zeroes[i - 1]
	ones[i] = ones[i - 1]
	if s[i - 1]:
		ones[i] += 1
	else:
		zeroes[i] += 1
for i in range(q):
	(l, r) = map(int, input().split())
	one = (power(2, ones[r] - ones[l] + (s[l - 1] == 1), MOD) - 1) % MOD
	two = (power(2, zeroes[r] - zeroes[l] + (s[l - 1] == 0), MOD) - 1) % MOD
	res = one * two % MOD
	res = (res + one) % MOD
	print(res)


(n, m) = map(int, input().split())
t = list(map(int, list(input())))
p = [0] + t[:]
mod = 10 ** 9 + 7
o = []
for i in range(n):
	p[i + 1] += p[i]
for _ in range(m):
	(l, r) = map(int, input().split())
	a = p[r] - p[l - 1]
	b = r - l + 1 - a
	o.append(str((pow(2, a + b, mod) - pow(2, b, mod)) % mod))
print('\n'.join(map(str, o)))


(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(1000000000.0 + 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)


from sys import *
ans = []
(n, q) = map(int, stdin.readline().split())
s = stdin.readline()
MOD = 1000000007
t = [0 for i in range(n + 1)]
t[0] = 0
for i in range(1, n + 1):
	t[i] = t[i - 1] + 1 if s[i - 1] == '1' else t[i - 1]
for i in range(q):
	(l, r) = map(int, stdin.readline().split())
	_sum = r - l + 1
	zero = _sum - t[r] + t[l - 1]
	res = (pow(2, _sum, MOD) - pow(2, zero, MOD)) % MOD
	ans.append(res)
stdout.write('\n'.join(map(str, ans)))


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
(n, q) = map(int, input().split())
t = input()
zero = [0] * n
ones = [0] * n
if t[0] == '0':
	zero[0] = 1
else:
	ones[0] = 1
for j in range(1, n):
	if t[j] == '0':
		zero[j] = zero[j - 1] + 1
		ones[j] = ones[j - 1]
	else:
		ones[j] = ones[j - 1] + 1
		zero[j] = zero[j - 1]
ans = []
for j in range(q):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if a == 0:
		totalone = ones[b]
	else:
		totalone = ones[b] - ones[a - 1]
	if a == 0:
		totalzero = zero[b]
	else:
		totalzero = zero[b] - zero[a - 1]
	x = totalone + totalzero
	ans.append(str((pow(2, x, mod) - pow(2, totalzero, mod) + mod) % mod))
sys.stdout.write('\n'.join(ans))


import sys
from math import floor, ceil
inp = lambda : sys.stdin.readline().strip()
MOD = 1000000000.0 + 7
(n, q) = map(int, inp().split())
s = inp()
d = [0] * (n + 1)
pwr2 = [0] * (n + 1)
pwr2[0] = 1
for i in range(1, n + 1):
	pwr2[i] = int(pwr2[i - 1] * 2 % MOD)
for i in range(n):
	t = 0
	if s[i] == '1':
		t = 1
	d[i + 1] = d[i] + t
while q != 0:
	q -= 1
	(l, r) = map(int, inp().split())
	one = d[r] - d[l - 1]
	zero = r - l + 1 - one
	ans = (pwr2[one + zero] - pwr2[zero] + MOD) % MOD
	print(int(ans))


import sys
import math
input = sys.stdin.readline

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
modi = 1000000007
ones = [0] * 100001
for i in range(1, 100001):
	ones[i] = (2 * ones[i - 1] + 1) % modi
zeroes = [1] * 100001
for i in range(1, 100001):
	zeroes[i] = 2 * zeroes[i - 1] % modi
(n, q) = map(int, input().split())
s = input()
cones = [0] * (n + 1)
for i in range(1, n + 1):
	if s[i - 1] == '1':
		cones[i] = cones[i - 1] + 1
	else:
		cones[i] = cones[i - 1]
for i in range(q):
	(l, r) = map(int, input().split())
	curr = cones[r] - cones[l - 1]
	ans = ones[curr] % modi
	ans = ans % modi * (zeroes[r - l + 1 - curr] % modi) % modi
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
t = list(map(int, list(input())))
p = [0] + t[:]
mod = 10 ** 9 + 7
o = []
for i in range(n):
	p[i + 1] += p[i]
for _ in range(m):
	(l, r) = map(int, input().split())
	a = p[r] - p[l - 1]
	b = r - l + 1 - a
	o.append(str((pow(2, a + b, mod) - pow(2, b, mod)) % mod))
print('\n'.join(map(str, o)))


from sys import *
mod = 1000000007
(n, q) = map(int, stdin.readline().split())
s = str(stdin.readline())
arr = []
count = 0
for i in s:
	if i == '1':
		count += 1
	arr.append(count)
ansarr = []
for i in range(q):
	(x, y) = map(int, input().split())
	if x == 1:
		total1 = arr[y - 1]
	else:
		total1 = arr[y - 1] - arr[x - 2]
	total0 = y - x + 1 - total1
	ans = pow(2, y - x + 1, mod) % mod
	ans = ((ans % mod - pow(2, total0, mod) % mod) % mod + mod) % mod
	ansarr.append(ans)
stdout.write('\n'.join(map(str, ansarr)))


from sys import stdin, stdout
(n, q) = map(int, input().split())
mod = 1000000007
o = []
s = []
r = m = 0
a = input()
for i in a:
	if i == '0':
		r += 1
	else:
		m += 1
	o.append(r)
	s.append(m)
z = [1]
for i in range(100000):
	z.append(z[-1] * 2 % mod)
for j in range(q):
	(l, r) = (int(j) for j in stdin.readline().split())
	m = r - l + 1
	zs = o[r - 1] - o[l - 1] + (a[l - 1] == '0')
	os = m - zs
	if zs != 0:
		print((z[os] - 1) % mod * (z[zs] % mod) % mod)
	else:
		print((z[os] - 1) % mod)


import math
(n, q) = [int(x) for x in input().split()]
qq = str(input())
s = [int(x) for x in qq]
prefix = [0] * n
prefix[0] = s[0]
temp = [0] * (n + 1)
temp[0] = 1
mod = pow(10, 9) // 1 + 7
for i in range(1, n):
	prefix[i] += prefix[i - 1] + s[i]
	temp[i] = 2 * (temp[i - 1] % mod) % mod
temp[n] = 2 * (temp[n - 1] % mod) % mod
ansarray = []
while q > 0:
	q -= 1
	(l, r) = [int(x) - 1 for x in input().split()]
	a = prefix[r] - prefix[l] + s[l]
	d = r - l + 1
	val1 = temp[d]
	val2 = temp[d - a]
	ansarray.append((val1 - val2) % mod)
print(*ansarray)


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 = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	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)


(n, q) = map(int, input().split())
s = input()
c0 = [0]
for i in s:
	c0.append(c0[-1] + (i == '0'))
M = 10 ** 9 + 7
ans = []
for i in range(q):
	(l, r) = map(int, input().split())
	z = c0[r] - c0[l - 1]
	on = r - l + 1 - z
	ans.append((pow(2, on, M) - 1) * pow(2, z, M) % M)
print('\n'.join(list(map(str, ans))))


from __future__ import print_function
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import log2
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, q) = gil()
a = gbs()
sp = [[0 for _ in range(n)] for _ in range(int(log2(n)) + 1)]
sp[0] = a
m = len(sp)
for i in range(1, m):
	d = 1 << i - 1
	for j in range(n):
		sp[i][j] = sp[i - 1][j] + (sp[i - 1][j + d] if j + d < n else 0)

def getSum(l, r):
	ans = 0
	while l <= r:
		bt = int(log2(r - l + 1))
		ans += sp[bt][l]
		delta = 1 << bt
		l += delta
	return ans
for _ in range(q):
	(l, r) = gil()
	one = getSum(l - 1, r - 1)
	zero = r - l + 1 - one
	ans = (pow(2, one, mod) - 1 + mod) % mod * pow(2, zero, mod)
	if ans >= mod:
		ans %= mod
	print(ans)


import sys
MOD = 10 ** 9 + 7
r = sys.stdin.readlines()
(n, q) = r[0].split(' ')
n = int(n)
q = int(q)
s = r[1]
c = [0] * (n + 1)
for i in range(n):
	c[i + 1] = c[i] + (s[i] == '1')
p2 = [1] * (2 * n + 1)
for i in range(1, 2 * n + 1):
	p2[i] = p2[i - 1] * 2 % MOD
out = []
for qq in range(q):
	(a, b) = r[qq + 2].split(' ')
	a = int(a)
	b = int(b)
	o = c[b] - c[a - 1]
	z = b - a + 1 - o
	ans = (p2[o + z] - p2[z]) % MOD
	out.append(str(ans))
sys.stdout.write('\n'.join(out))