MUZIDA - Muzidabutur

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 109 + 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

Added by:Fudan University Problem Setters
Date:2009-05-31
Time limit:1s
Source limit:3333B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Resource:Not my own problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.