Problem Description

$ square1001 $: "In $ E869120 $, all characters are different, but in $ square1001 $, there are even two characters that match!"

$ E869120 $: "Does that mean the number of distinct substrings is also different?"

$ square1001 $: "For example, in '1001', the '0' at the 2nd character and the '0' at the 3rd character are duplicated, aren't they? ('1' is also like that!)"

So, this time, please list all substrings of string S and count the total number of characters when duplicates are merged into one.

For example, in the case of "aba", there are 6 possible substrings: {"a", "b", "a", "ab", "ba", "aba"}. However, since "a" is duplicated,

there are 5 distinct substrings considered.

The total number of characters in {"a", "b", "ab", "ba", "aba"} is 1 + 1 + 2 + 2 + 3 = 9.

Note: The answer may not fit into a 32-bit integer.

• $ a, b, c, ab, bc, abc $ are substrings of $ abc $, and the total is 10 characters.

• Be aware of duplicates.

Input Format

Input is given from the standard input in the following format:

$ S $

• The first line contains the string $ S $ to be examined.

Output Format

Output should follow the standard output in the following format:

• Output the total length of the distinct substrings (counting duplicates as one) in one line.
• Note that the answer may not fit into a 32-bit integer.

Sample Input and Output

Sample Input #1

abc

Sample Output #1

10

Sample Input #2

aaqqz

Sample Output #2

33

Sample Input #3

atcoder

Sample Output #3

84

Notes/Hints

Constraints

• $1 \leq |S| \leq 100,000$
• The string contains only lowercase alphabets.

Subtasks

Subtask $ 1 $ \[ $ 15 $ points \]

• Satisfies $1 \leq |S| \leq 100$.

Subtask $ 2 $ \[ $ 35 $ points \]

• Satisfies $1 \leq |S| \leq 2,000$.

Subtask $ 3 $ \[ $ 50 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分