P哥旋转

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$ 分全部没有）。