Harry Potter and the Order of Phoenix
Tag(s):

## Medium, Medium-Hard

Problem
Editorial
Analytics

As you know, Professor Umbridge (Yes, the plump pink toad) is ruthless. She had asked Harry to write "I must not tell lies", didn't she? Well, not this time.

This time she gave him a string S and Q queries each of which contains 2 intergers l and r . For each query he has to find the summation of ( length (P) ^ distinct (P) ) for all possible substrings P of the substring S[l,r], where length (P) is the length of the substring, distinct(P) is the number of distinct characters in the substring P and "^" denotes the power/exponent operation.

Well, Harry didn't take arithmancy, did he? And he doesn't have any spell to do this too. I guess coding in the magical world would have been of help. But nevertheless, he asks you for help.

## Input

First line contains a string S. Next line contains a number Q. Each of next Q lines contain two number l and r.

## Output

Print Q lines, each of which contains the required answer mod (10^9 + 7).

1<=N<=55555

1<=Q<=55555

1<=l,r<=N

## Note

Use fast I/O.

Print answer mod (10^9 + 7).

SAMPLE INPUT
jktqroxm
5
1 5
2 4
1 4
1 1
3 5
SAMPLE OUTPUT
3739
38
326
1
38
Explanation

### Testcase2:

Substring (2,4) is "ktq". All possible substrings are "k","t","q","kt","tq","ktq". So, required sum is 1^1 + 1^1 + 1^1 + 2^2 + 2^2 + 3^3 = 1+1+1+4+4+27 = 38.

Time Limit: 3.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Epiphany 6.2

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Greedy Algorithms
• Math > Number Theory
• Algorithms > Dynamic Programming