Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Banh-mi

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputJATC 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 03:37:02 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|