Given a string S of lowercase Latin letters. You are to answer Q queries: given l and r (1 <= l <= r <= |S|), count the number of distinct non-empty subsequences of the substring S[l..r].

Input

Multiple test cases. For each test case:

The first line of input contains a string S.(|S| <= 40000). The second line contains a single integer Q (Q<= 100000). Q lines follow, each contains two space separated integers l and r.

Input terminates by EOF.

Input data is almost uniformly-random generated, the number of "large" test cases is relatively small.

Output

For each query output one line - the answer, modulo 10⁹ + 2015.

Example

Input:
aabababb
5
1 8
1 4
3 5
5 7
3 8
aaccbb
5
1 6
3 4
2 5
1 4
3 6
Output:
63
9
6
6
27
26
2
11
8
8