CF1062C.Banh-mi

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$.

JATC 非常喜爱越南美食“法棍三明治”（Banh-mi）。他对 Banh-mi 的热爱如此之深，以至于每天早餐必吃。今天早上，和往常一样，他买了一个 Banh-mi，并决定以一种特别的方式享用它。

首先，他将 Banh-mi 切成 $n$ 个部分，将它们排成一行，并从 $1$ 到 $n$ 编号。对每个部分 $i$，他定义其美味度为 $x_i \in \{0, 1\}$。JATC 将逐一吃掉这些部分。在每一步中，他任选一个尚未被吃掉的部分并吃掉它。假设他吃掉的是第 $i$ 个部分，则他的愉悦值增加 $x_i$，且所有剩余未吃部分的美味度也均增加 $x_i$。JATC 的初始愉悦值为 $0$。

例如，假设三个部分的美味度为 $[0, 1, 0]$。若 JATC 先吃掉第二个部分，则他的愉悦值变为 $1$，剩余部分的美味度变为 $[1, \_, 1]$（其中 $\_$ 表示该部分已被吃掉）。接着，若他吃掉第一个部分，则愉悦值变为 $2$，剩余部分的美味度变为 $[\_, \_, 2]$。最后吃掉第三个部分后，JATC 的总愉悦值变为 $4$。

然而，JATC 并不想吃掉全部部分，而是想留下一些以后再吃。他向你提出 $q$ 个询问，每个询问包含两个整数 $l_i$ 和 $r_i$。对每个询问，你需要告诉他：若他仅吃掉下标在区间 $[l_i, r_i]$ 内的所有部分（按某种顺序），所能获得的最大愉悦值是多少。

所有询问相互独立。由于询问答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

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.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 100\,000$）。

第二行包含一个长度为 $n$ 的字符串，每个字符为 '0' 或 '1'。其中第 $i$ 个字符表示第 $i$ 段的美味度。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示对应查询的区间。

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

输出 $q$ 行，其中第 $i$ 行包含一个整数——第 $i$ 个查询的答案对 $10^9 + 7$ 取模的结果。

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.

在第一个例子中：

• 对于查询 $1$：JATC 吃掉这些部件的最佳方式之一是按以下顺序：$1$、$4$、$3$、$2$。
• 对于查询 $2$：顺序 $3$、$4$ 和 $4$、$3$ 均给出相同的结果。

在第二个例子中，以任意顺序吃掉这些部件均会得到相同的结果。