子串编码值

难度：T4

【知识点：字符串哈希】

前置知识：字符串哈希及其冻结前置单元。

题目描述与输入

输入非空小写串$s$、查询数$q$，再输入$q$行$l$、$r$，为$0$起点半开区间。编码$a=1..z=26$，$B=131$，$M=1000000007$。

规则说明

半开区间 $[l,r)$ 包含位置 $l$，不包含位置 $r$，下标从 $0$ 开始。设截取的子串依次对应整数 $c_1,c_2,\ldots,c_k$，本题编码值规定为 $(c_1B^{k-1}+c_2B^{k-2}+\cdots+c_k)\bmod M$，取非负余数。例如 ab 编码为 $1\times131+2=133$。每次截取后都按子串自身的长度编码。

输出

每问输出对应子串的多项式哈希值。

数据范围

$1$<=|$s$|<=$2000$；$1$<=$q<=2000$；$0$<=$l<r$<=|$s$|；第二组区间同样合法。

样例输入

abac
3
0 2
1 3
0 4

样例输出

133
263
2282547

样例说明

前缀多项式与幂表均预处理，截取时减掉对齐前缀。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。