Super Functional Strings

We define a function, , on a string, , as follows:

where:

denotes the number of characters in string .
denotes the number of distinct characters in string .

Consuela loves creating string challenges and she needs your help testing her newest one! Given a string, , consisting of lowercase letters, compute the summation of function (provided above) over all possible distinct substrings of . As the result is quite large, print it modulo .

Input Format

The first line contains a single integer, , denoting the number of test cases.
Each of the subsequent lines contains a string, .

Constraints

The sum of over all test cases does not exceed .

Scoring

for of test data.
for of test data.
for of test data.

Output Format

For each test case, print the answer modulo .

Sample Input

3
aa
aba
abc

Sample Output

3
19
38

Explanation

Test 0:

and are the only distinct substrings.

Test 1:

, , , , and are the only distinct substrings.