Strange Substrings

Given a string \( s \) consisting of lowercase letters, we define:

• \( W(s) \): the set of all non-empty substrings (continuous segments) of \( s \). For example, \( W(\texttt{abba}) = \{\texttt{a},\texttt{b},\texttt{ab},\texttt{bb},\texttt{ba},\texttt{abb},\texttt{bba},\texttt{abba}\} \).
• \( Y(s) \): the set of all non-empty subsequences of \( s \). Note that \( Y(s) \) always contains \( W(s) \) but in general can be larger (for instance, for \( s=\texttt{abba} \), \( Y(\texttt{abba}) = W(\texttt{abba}) \cup \{\texttt{aa},\texttt{aba}\} \)).

A string \( s \) is called strange if \( W(s)=Y(s) \); that is, every non-empty subsequence of \( s \) is also a substring of \( s \). It can be shown that this property is equivalent to the condition that, for every letter in \( s \), all occurrences of that letter appear in one contiguous block. For example, abba is not strange because the letter a appears separated by other letters, while abb is strange.

The strangeness degree of a string \( s \) is defined as the number of distinct strange substrings contained in \( s \) (i.e. the number of strange strings in \( W(s) \)). For example, for \( s=\texttt{abba} \), all substrings except \( \texttt{abba} \) itself are strange, so its strangeness degree is 7.

Your task is to compute the strangeness degree of a given string \( s \).

inputFormat

The input consists of a single line containing the string \( s \), which is composed exclusively of lowercase English letters.

outputFormat

Output a single integer representing the strangeness degree of \( s \) — the number of distinct strange substrings of \( s \).

sample

abba

7