JATC 喜欢 Banh-mi(越南菜)。他对 Banh-mi 的喜爱如此之深,以至于他总是把它当早餐。今天早上,他像往常一样买了一份 Banh-mi 并决定以一种特殊的方式享用它。
首先,他将 Banh-mi 分成 $$$n$$$ 部分,将它们排成一行,并从 $$$1$$$ 到 $$$n$$$ 进行编号。对于每个部分 $$$i$$$,他将该部分的美味程度定义为 $$$x_i \in \{0, 1\}$$$。 JATC将把这些部分一一吃掉。每一步,他都会选择任意剩余的部分并吃掉它。假设该部分是第$$$i$$$部分,那么他对Banh-mi的享受将增加$$$x_i$$$,并且所有剩余部分的美味也将增加$$$x_i$$$。 JATC初始享受金额为$$$0$$$。
例如,假设 $$$3$$$ 部分的美味程度为 $$$[0, 1, 0]$$$。如果JATC吃掉第二部分,那么他的享受将变成$$$1$$$,而剩余部分的美味将变成$$$[1, \_, 1]$$$。接下来,如果他吃掉第一部分,那么他的享受将变成$$$2$$$,其余部分将变成$$$[\_, \_, 2]$$$。吃完最后一部分,JATC的享受就会变成$$$4$$$。
然而,JATC 并不想吃掉所有的部分,而是保存一些以供以后使用。他给你$$$q$$$查询,每个查询由两个整数$$$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$$$ 行,其中第 $$$i$$$ 包含一个整数 - 第 $$$i$$$ 查询的答案以 $$$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
注意
在第一个示例中:
- 对于查询 $$$1$$$:JATC 吃这些部分的最佳方法之一是按以下顺序:$$$1$$$、$$$4$$$、$$$3$$$、$$$2$$$。
- 对于查询 $$$2$$$:$$$3$$$、$$$4$$$ 和 $$$4$$$、$$$3$$$ 排序给出相同的答案。
在第二个示例中,任何吃零件的顺序都会得到相同的答案。