给定一个长度为 $n$ 的只包含前 $9$ 个小写字母的字符串 $s$，$q$ 个询问 $l,r$，询问 $s[l\dots r]$ 中有多少本质不同的子序列。答案对 109+7 10 ^ 9 + 7 109+7 取模。
$s[l\dots r]$ 的子序列 {p1,p2,⋯,pk} \{ p_1, p_2, \cdots, p_k \} {p1,p2,⋯,pk} 需要满足：l≤p1l≤p1<p2<⋯<pk≤r。
两个子序列 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$。
第二行一个整数 $q$。
接下来 $q$ 行描述一个询问 li,ri l_i, r_i li,ri。

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

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