CF1062C 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,4,3,2$。 对第2个询问：以$3,4$或$4,3$的顺序都可以得到同样的答案。 任何顺序都能够得到相同的答案。