We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- Prepare
- Algorithms
- Strings
- Super Functional Strings

# Super Functional Strings

# 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.