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.
First line contains a string S. Next line contains a number Q. Each of next Q lines contain two number l and r.
Print Q lines, each of which contains the required answer mod (10^9 + 7).
Use fast I/O.
Print answer mod (10^9 + 7).
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.