Distinct Sorted Substrings

You are given a string S. For every substring of S, rearrange its characters in lexicographical order and then count the number of distinct sorted substrings.

For example, if S = "abc", the substrings and their sorted forms are:

• "a" → "a"
• "ab" → "ab"
• "abc" → "abc"
• "b" → "b"
• "bc" → "bc"
• "c" → "c"

The answer is the number of unique sorted substrings, which in this case is 6.

In mathematical terms, if you consider all substrings S_i,j for indices i and j (with 1 \le i \le j \le n, where n is the length of S), then the task is to compute:

$$\text{Answer} = \left| \{ \text{sort}(S_{i,j}) : 1 \le i \le j \le n \} \right|$$

inputFormat

A single line containing a non-empty string S. The characters of S can be assumed to be ASCII letters.

outputFormat

A single integer denoting the number of distinct sorted substrings obtained by sorting each substring of S in lexicographical order.## sample

abc

6