给定一个长度为 n n n 的只包含前 9 9 9 个小写字母的字符串 s s s，q q q 个询问 l,r l,r l,r，询问 s[l…r] s[l \ldots r] s[l…r] 中有多少本质不同的子序列。答案对 109+7 10 ^ 9 + 7 109+7 取模。
s[l…r] s[l \ldots r] s[l…r] 的子序列 {p1,p2,⋯,pk} \{ p_1, p_2, \cdots, p_k \} {p1,p2,⋯,pk} 需要满足：l≤p1<p2<⋯<pk≤r l="" \leq="" p_1="" l≤p1<p2<⋯<pk≤r</p2<⋯。
两个子序列 p,q p, q p,q 是本质不同的，当且仅当其长度不同，或存在一个 i i i，满足 s[pi]≠s[qi] s[p_i] \neq s[q_i] s[pi]≠s[qi]。

第一行一个字符串 s s s。
第二行一个整数 q q q。
接下来 q q q 行描述一个询问 li,ri l_i, r_i li,ri。

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

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