题目描述

新任市长$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$行，每行一个整数，表示对应的询问的答案。

样例

【样例 1 输入】

5 2
11100
1 3
4 5

【样例 1 输出】

10
2

数据范围与提示

样例1解释

当地所有片区能获得的能源分别为：$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$。