Count Non-Mode Substrings

You are given a string s of length n consisting only of lowercase letters. Your task is to count the number of non-empty substrings of s that are non-mode substrings.

A non-empty substring of s is defined as follows: for any two integers \(i\) and \(j\) with \(1 \leq i \leq j \leq n\), the contiguous sequence \(s_i s_{i+1} \cdots s_j\) is a substring of s.

A substring \(a\) of s is called a non-mode substring if the frequency of its most frequent character does not exceed \(\lfloor \frac{|a|}{2} \rfloor\), where \(|a|\) denotes the length of \(a\) and \(\lfloor x \rfloor\) denotes the greatest integer less than or equal to \(x\).

For example, if s = "abcde", then the substrings "ab", "bcde", "c", and "abcde" are valid substrings while strings like "acd" or "f" are not substrings of s. Note that for any single character substring, since \(\lfloor 1/2 \rfloor = 0\) and the character appears once, these substrings are not considered non-mode substrings.

inputFormat

The input consists of a single line containing the string s (consisting only of lowercase English letters).

outputFormat

Output a single integer representing the number of non-mode substrings of s.

sample

a

0