给定一个长度为 n 的字符串 s，保证 s 仅包含小写字母，求 s 的非空子串中非众数串的个数。

定义：非空子串

用 s_i 表示 s 中的第 i 个字符（1 \leq i \leq n）。任取两个整数 i, j（1 \leq i \leq j \leq n），将 $si, s{i + 1}, \cdots, s_{j} 截取出来按原序排列作为一个新的字符串，则这个字符串叫做 s$ 的非空子串。
例如，当 s = \texttt{abcde} 时，\texttt{ab}, \texttt{bcde}, \texttt{c}, \texttt{abcde} 都是 s 的非空子串，而 \texttt{acd}, \texttt{f}, \texttt{ngioasd}, \texttt{" "} 都不是 s 的非空子串。

定义：非众数串

若字符串 a 中出现次数最多的字符出现的次数不超过 \lfloor \frac{|a|}{2} \rfloor，则称字符串 a 为一个非众数串。其中 \lfloor x \rfloor 代表 \leq x 的最大整数，|a| 代表 a 的长度。

一行一个字符串，表示 s。

一行一个整数，表示答案。

对于 100\% 的数据，1 \le n \le 500，字符串由小写字母组成。

luogu