You're given a string S. Let's consinder the following function F, which for given string computes integer number: 1. If string is empty, return 0; 2. Otherwise, return F(substring(S,0,(length of S)-1)) * 37 + s[i]; Where S[i] is zero for 'a', 1 for 'b', 2 for 'c' ... 25 for 'z'. For a given string S, compute the value of F(S). Input data specification First string of the file contains number of test cases T. Then for each of T cases there's one line with string S itself. Output data specification For each test case produce one line of output with the value of F for a given string. As this value might be very large, output it modulo 1000007; Constrains: 1 <= Lenght of S <= 30000 S consists only of lowercase english letters Sample input: 3 a ab ba Sample output: 0 1 37