题目描述

译自 ROIR 2016 Day1 T3. Странные строки

考虑一个由小写拉丁字母组成的字符串 $s$。例如，字符串 $\texttt{abba}$ 就是一个这样的字符串。

字符串 $s$ 的子串是指由 $s$ 中一个或多个连续字符组成的字符串。我们用 $W(s)$ 表示由 $s$ 的所有可能子串组成的集合。每个子串在该集合中最多只出现一次，即使它在字符串 $s$ 中出现了多次。

例如，$W(\texttt{abba}) = \{\texttt{a}, \texttt{b}, \texttt{ab}, \texttt{ba}, \texttt{bb}, \texttt{abb},\texttt{bba}, \texttt{abba}\}$。

字符串 $s$ 的子序列是指通过从 $s$ 中删除任意数量的字符后得到的字符串。我们用 $Y(s)$ 表示由 $s$ 的所有可能子序列组成的集合。同样，每个子序列在 $Y(s)$ 中也只出现一次，即使可以通过多种方式删除字符得到。由于 $s$ 的任何子串也是其子序列，因此 $Y(s)$ 包含 $W(s)$，但可能还包含其他字符串。

例如，$Y(\texttt{abba}) = W(\texttt{abba}) \cup \{\texttt{aa}, \texttt{aba}\}$。符号 $\cup$ 表示集合的并集。

如果对于字符串 $s$ 满足 $W(s) = Y(s)$，我们称该字符串为奇异字符串。因此，字符串 $\texttt{abba}$ 不是奇异字符串，而例如字符串 $\texttt{abb}$ 是奇异字符串，因为 $W(\texttt{abb}) = Y(\texttt{abb}) = \{\texttt{a}, \texttt{b}, \texttt{ab}, \texttt{bb}, \texttt{abb}\}$。

我们定义字符串的奇异度为它的不同奇异子串的数量。在计算奇异度时，即使某个子串在 $s$ 中作为子串出现多次，也只计算一次。例如，对于字符串 $\texttt{abba}$，其奇异度为 $7$，因为除了整个字符串外，其所有子串都是奇异字符串。

你的任务是编写一个程序，根据给定的字符串 $s$，确定其奇异度。

输入格式

输入文件包含一个由小写拉丁字母组成的字符串 $s$，长度在 $1$ 到 $200000$ 之间。

输出格式

输出文件应包含一个整数，表示输入文件中给定字符串的奇异度。

abba

7

数据范围与提示

详细子任务附加限制及分值如下表所示：