A kitten is slacking off.
A senior student gives the kitten a string $s$ consisting of lowercase letters and poses $q$ queries, each consisting of a pair $l, r$. For each query, find the number of distinct subsequences in $s[l, r]$.
Since the kitten is not very skilled, the senior student has lowered the requirements: output the answer modulo $10^9 + 7$. However, the kitten still needs you to check the answers.
Input
The first line contains a non-empty string $s$. The second line contains a positive integer $q$. The next $q$ lines each describe a query $l, r$.
Output
Output $q$ lines, each representing the answer to the corresponding query.
Constraints
Let $n$ be the length of $s$.
- For the first 20% of the data, $n \le 20$.
- For the first 40% of the data, $n \le 1000$.
- For the first 60% of the data, $n \le 10^4$.
- For the first 80% of the data, $n, q \le 10^5$, and only the first 9 lowercase letters are used.
- For 100% of the data, $n, q \le 10^6$, $1 \le l \le r \le n$.
Examples
Input 1
bacbbab 3 4 6 1 7 1 3
Output 1
5 68 7