Given a string S, print the hash code of that string using Polynomial Hashing. Note: Use prime number = 31 and print the answer mod 1000000007.
Input Format
The first line contains an integer T denoting the number of test cases. T lines follow each containing a string S.
Output Format
Print an integer (the hashcode of the string) mod 1000000007 and take prime number 31 for hashing.
Constraints
String s consists of only lowercase English alphabets |S| <= 10^5
Example
Input
6 ab abc abcd abc xyz pqr
Output
63 2946 122110 2946 25785 17841