C.能源 energy

题目描述

新任市长 $Chihiro$ 给 $Introl$ 传真了当地行政规划图，其用长度为 $N$ 字符串 $S$ 表示，其中 $0$ 和 $1$ 分别表示空地和城区。

定义 $x_i$ 和 $x_j$ 的 $φ$ 距离为 $\lvert x_i-x_j \rvert+1$ 。

$Introl$ 规划在空地和城区分别建设风车和光伏发电板，对于一处空地其每天能获取的风能为 $E_{wind}^2$ ，对于一处城区其每天能获取的光能为 $E_{solar}^3$ 。

最大的 $E_{wind}$ 满足到该空地的 $φ$ 距离不超过最大的 $E_ {wind}$ 的地方在行政规划片区内且为空地。

最大的 $E_ {solar}$ 满足到该城区的 $φ$ 距离不超过最大的 $E_ {solar}$ 的地方在行政规划片区内且为城区。

$Chihiro$ 将提出 $M$ 次询问，对于片区 $[L,R]$ 每天共能获取多少能源，答案对 $1e9+7$ 取模。

第一行两个整数 $N$ 和 $M$ ，分别表示字符串 $S$ 的长度和询问次数。

第二行仅一个字符串 $S$ 。

接下来 $M$ 行，每行给出 $L,R$ 表示一组询问。

输出共有 $M$ 行，每行一个整数，表示对应的询问的答案。

10
2

当地所有片区能获得的能源分别为： $1,8,1,1,1$ 。

对于片区 $[1,3]$ 能获得的能源为 $1+8+1=10$ 。

对于片区 $[4,5]$ 能获得的能源为 $1+1=2$ 。

对于 $30$ %的数据， $1 \leq N,M \leq 10^3$ 。

对于另外 $20$ %的数据， $S$ 仅包含 $0$ 。

对于 $100$ %的数据， $1 \leq L \leq R \leq N,M \leq10^6$ 。