Count Equivalently Eliminable Substrings

Given a string $S$ consisting only of lowercase English letters, we say that a string is equivalently eliminable if it can be reduced to an empty string by repeatedly removing any two identical characters (i.e. a pair of equal characters) at a time.

A substring of $S$ is defined as some contiguous segment obtained by deleting a (possibly empty) prefix and a (possibly empty) suffix of $S$.

Your task is to count the number of substrings of $S$ that are equivalently eliminable.

Note: A string is equivalently eliminable if and only if, for every character, its frequency in the string is even.

In other words, if we denote by $f_c(S')$ the frequency of character $c$ in substring $S'$, then $S'$ can be eliminated if and only if $$\forall c \in \{a,\ldots,z\},\; f_c(S')\equiv 0\, (\bmod\,2).$$

inputFormat

The input consists of a single line containing the string $S$.

It is guaranteed that $S$ contains only lowercase English letters.

outputFormat

Output a single integer, which is the number of substrings of $S$ that are equivalently eliminable.

sample

a

0