题目背景

P哥开始学字符串了！

题目描述

P 哥学会了字符串处理的新方法——旋转。

“旋转”是这样一种操作：将原字符串最后面的字符抹去，然后把它加到最前面，得到一个新串。

P 哥可以进行无数次“旋转”操作，让得到的新串中本质不同的回文子串尽可能多。

两个回文串本质不同，当且仅当它们长度不同，或至少有一个相同位置的字符不同。

现在 P 哥得到了一个串 $S$，请你通过“旋转”操作帮 P 哥达成他的目标（即上面的加粗字体部分），并输出新串中不同的回文子串的个数。

输入格式

输入共一行，代表串 $S$，保证只有小写英文字母。

输出格式

输出一个整数表示答案。

ioimoio

7

fcfcfcfcfczxqprvvlpstpasxvpyyhaejxehdlhckmwmibsjwqbmfzlwpjqjghmlxunefabkpryqxbkqridpqrzemvfcfcfcfcfc

47

提示

设 $n$ 为串 $S$ 的长度。

• 对于前 $20\%$ 的数据，$n \le 100$。
• 对于前 $40\%$ 的数据，$n \le 2000$。
• 对于另 $10\%$ 的数据，保证得出正确答案不用进行旋转。
• 对于 $100\%$ 的数据，$n \le 1.5\times 10^6$。

此外，对于后 $50\%$ 的数据，保证串 $S$ 的非随机部分长度不超过 $5000$。

注意：本题采用 subtask 方式计分。前 $50\%$ 的数据是 subtask#1，该 subtask 采用加和的方式计分（你可以认为是传统计分方式）。后 $50\%$ 的数据是 subtask#2，该 subtask 采用取 $\min$ 的方式计分（即只要错一个点，后 $50$ 分全部没有）。