题目描述

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

样例

input

bacbbab
3
4 6
1 7
1 3

output

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 $。