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

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个长度为 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