We define a function, , on a string, , as follows:
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 .
The first line contains a single integer, , denoting the number of test cases.
Each of the subsequent lines contains a string, .