Strange Strings

Consider a string $s$ consisting of lowercase Latin letters. One example of such a string is «abba».

A substring of $s$ is a string formed from one or more consecutive characters of $s$. Let $W(s)$ be the set of all substrings of $s$. Each substring appears in this set at most once, even if it occurs several times in $s$.

For example, $W(\text{«abba»}) = \{\text{«a»}, \text{«b»}, \text{«ab»}, \text{«ba»}, \text{«bb»}, \text{«abb»}, \text{«bba»}, \text{«abba»}\}$.

A subsequence of $s$ is a string obtained from $s$ by deleting any number of characters. Let $Y(s)$ be the set of all subsequences of $s$. As with $W(s)$, each subsequence of $s$ is included in $Y(s)$ exactly once, even if it can be obtained by several different ways of deleting characters from $s$. Since every substring of $s$ is also a subsequence of $s$, the set $Y(s)$ contains $W(s)$, but it may also contain other strings.

For example, $Y(\text{«abba»}) = W(\text{«abba»}) \cup \{\text{«aa»}, \text{«aba»}\}$. The symbol $\cup$ denotes the union of sets.

Call a string $s$ strange if $W(s) = Y(s)$. For instance, «abba» is not strange, but «abb» is, since $W(\text{«abb»}) = Y(\text{«abb»}) = \{\text{«a»}, \text{«b»}, \text{«ab»}, \text{«bb»}, \text{«abb»}\}$.

Call the strangeness of a string the number of its distinct strange substrings. When computing the strangeness, a substring is counted once, even if it occurs several times as a substring of $s$. For example, the strangeness of «abba» is 7: every substring of it except the whole string is strange.

Write a program that, given a string $s$, determines its strangeness.

The input file contains a string $s$ consisting of lowercase Latin letters. The length of the string is between 1 and 200,000.

The output file must contain a single integer: the strangeness of the string given in the input file.