Distinct Substrings

You are given a string s. Your task is to count the number of distinct substrings present in the string. A substring is defined as a contiguous sequence of characters within s. Note that even if the same sequence appears multiple times, it is counted only once.

For a string of length n, the total number of substrings (not necessarily distinct) is given by the formula $$\frac{n(n+1)}{2}$$, but here you need to count only the unique ones.

Examples:

• For s = "abac", the answer is 9.
• For s = "aaa", the answer is 3.
• For s = "racecar", the answer is 25.

Solve the problem using standard input and output.

inputFormat

The input consists of a single line containing the string s. The string will not contain any spaces and its length is moderate.

outputFormat

Output a single integer representing the number of distinct substrings of s.

## sample

abac

9

</p>