Banh-mi

题意翻译

## 题目描述 JATC很喜欢吃越式法包(一种越南食品)。他总是把它当早餐吃，因为他实在是太喜欢了。这天早上，像以往一样，他买了一个越式法包，并且决定以一种特殊的方法吃掉它。 首先，他把越式法包分为$n$块，并把它们排成一行，从$1$到$n$标号。对于每一块，他定义第$i$块的_口感_为$x_i∈\{0,1\}$。JATC正准备将它们一个接一个地吃掉。每一次，他随意选择剩下的一块吃掉。比如说他选择了第$i$块，那么他的_愉悦度_就会增加$x_i$，并且所有剩下的块的_口感_也会增加$x_i$。最初，JATC的_愉悦度_等于0。 举个例子，假设$3$块越式法包的_口感_分别为$[0,1,0]$。如果JATC先吃掉第二块，他的_愉悦度_会变为$1$，其余块的_口感_则变为$[1,\_,1]$。接下来如果他吃掉第一块，他的_愉悦度_会变为$2$，剩下的块的_口感_变为$[\_,\_,2]$。吃掉最后一块后，JATC的_愉悦度_变为$4$。 然而，他不想吃掉所有的越式法包块儿，想留一些以后吃。他给了你$n$个询问，每个询问由两个整数$l_i$和$r_i$组成。对于每个询问，请告诉他当他以某种顺序吃掉区间$[l_i,r_i]$的所有块后，最大的愉悦度是多少。 每个询问都是互相独立的。由于答案可能很大，请对$10^9+7$取模。 ## 输入格式 第一行包含两个整数$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)$——每个询问的区间。 ## 输出格式 输出$q$行，每行一个整数——答案对$10^9+7$取模之后的结果。 #### 样例1说明 对第1个询问：一种最佳的方案顺序为：$1,4,3,2$。 对第2个询问：以$3,4$或$4,3$的顺序都可以得到同样的答案。 #### 样例2说明 任何顺序都能够得到相同的答案。

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4 2
1011
1 4
3 4

输出样例 #1

14
3

输入样例 #2

3 2
111
1 2
3 3

输出样例 #2

3
1

说明

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.