Counting Special Substrings

You are given a string S. Your task is to count the number of substrings of S that start and end with the same character. A substring is defined as a contiguous sequence of characters within the string. Note that the empty string should be considered as containing 0 valid substrings.

Hint: For a given character, if it appears f times in the string, then the number of substrings that start and end with that character is given by the formula: \(\frac{f(f+1)}{2}\).

inputFormat

The input consists of a single line containing the string S. The string may be empty and will consist of lowercase English letters.

outputFormat

Output a single integer representing the number of substrings of S that start and end with the same character.## sample

a

1