Count Matching-Ends Substrings

Given a string s consisting only of lowercase English letters, count the number of substrings that start and end with the same character. A substring is any contiguous sequence of characters within s.

You can think of the answer mathematically as: $$\sum_{c \in \{a,\ldots,z\}} \frac{n_c (n_c+1)}{2},$$ where \(n_c\) is the frequency of character \(c\) in s. However, you do not have to compute the frequencies explicitly; a brute force or double-loop solution will suffice under the given constraints.

inputFormat

Input is read from standard input. The input consists of a single line containing a string s, which is composed of lowercase English letters only.

outputFormat

Output to standard output a single integer: the number of substrings of s that start and end with the same character.## sample

abcab

7