Good Substrings

A string composed solely of lowercase letters is defined as good if its first and last characters are the same. Given a string s, your task is to determine how many substrings of s are good.

Note: A substring is a contiguous sequence of characters within a string. For example, the string abc has 7 substrings: the empty string (which contains no character), a, ab, abc, b, bc, and c. The empty substring is not considered good since it does not have a first or last character.

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

inputFormat

The input consists of a single line containing a string s made up of lowercase English letters.

outputFormat

Output a single integer representing the number of good substrings in s.

sample

abc

3