Unique Substrings

Given a string \(S\) of length \(n\), your task is to count the total number of unique non-empty substrings that appear in \(S\). A substring is a contiguous sequence of characters within the string. Note that if all substrings are distinct, their total count is given by the formula \(\frac{n(n+1)}{2}\), but when there are repetitions, the count will be lower.

Examples:

• For S = "abc", the unique substrings are "a", "b", "c", "ab", "bc", "abc" resulting in a count of 6.
• For S = "aaaa", the unique substrings are "a", "aa", "aaa", "aaaa" resulting in a count of 4.

Read the input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of a single line containing the string (S). The string can be empty. Read the string from standard input (stdin).

outputFormat

Output a single integer which is the number of unique non-empty substrings in the given string (S). Print the result to standard output (stdout).## sample

abc

6