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

时间限制1500ms

内存限制512MB

通过 / 提交0/0

题目描述

给定一个长度为 $ 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 $ 行，依次表示每个询问的答案。

输入 #1

bacbbab
3
4 6
1 7
1 3

输出 #1

5
68
7

C++ 编辑器

输入

输出