「2017 山东一轮集训 Day6」子序列

传统 1500 ms 512 MiB

$305$ 通过 $644$ 提交

题目描述

给定一个长度为 $n$ 的只包含前 $9$ 个小写字母的字符串 $s$，$q$ 个询问 $l,r$，询问 $s[l \ldots r]$ 中有多少本质不同的子序列。答案对 $10^9 + 7$ 取模。

$s[l \ldots r]$ 的子序列 $\{ p_1, p_2, \cdots, p_k \}$ 需要满足：$l \leq p_1 < p_2 < \cdots < p_k \leq r$。

两个子序列 $p, q$ 是本质不同的，当且仅当其长度不同，或存在一个 $i$，满足 $s[p_i] \neq s[q_i]$。

输入格式

第一行一个字符串 $s$。

第二行一个整数 $q$。

接下来 $q$ 行描述一个询问 $l_i, r_i$。

输出格式

输出 $q$ 行，依次表示每个询问的答案。

样例

输入

bacbbab
3
4 6
1 7
1 3

输出

5
68
7

数据范围与提示

对于 $20\%$ 的数据，$n \leq 20$；
对于 $40\%$ 的数据，$n \leq 1000$；
对于 $60\%$ 的数据，$n \leq 10000$；
对于 $100\%$ 的数据，$1 \leq n, q \leq 100000$，$1 \leq l \leq r \leq n$。