Description

P-bro has learned a new method for string processing: rotation.

A “rotation” is an operation like this: remove the last character of the original string, then add it to the very front, obtaining a new string.

P-bro can perform the “rotation” operation infinitely many times, in order to make the number of essentially different palindromic substrings in the resulting new string as large as possible.

Two palindromic strings are essentially different if and only if their lengths are different, or there exists at least one position where the characters are different.

Now P-bro has obtained a string $S$. Please help P-bro achieve his goal through “rotation” operations (i.e., the bolded part above), and output the number of different palindromic substrings in the new string.

Input Format

The input consists of one line, which is the string $S$, guaranteed to contain only lowercase English letters.

Output Format

Output one integer, representing the answer.

ioimoio

7

fcfcfcfcfczxqprvvlpstpasxvpyyhaejxehdlhckmwmibsjwqbmfzlwpjqjghmlxunefabkpryqxbkqridpqrzemvfcfcfcfcfc

47

Hint

Let $n$ be the length of string $S$.

• For the first $20\%$ of the testdata, $n \le 100$.
• For the first $40\%$ of the testdata, $n \le 2000$.
• For another $10\%$ of the testdata, it is guaranteed that you can obtain the correct answer without performing any rotation.
• For $100\%$ of the testdata, $n \le 1.5\times 10^6$.

In addition, for the last $50\%$ of the testdata, it is guaranteed that the length of the non-random part of string $S$ does not exceed $5000$.

Note: This problem uses subtask scoring. The first $50\%$ of the testdata is subtask#1, and this subtask uses additive scoring (you may consider it as traditional scoring). The last $50\%$ of the testdata is subtask#2, and this subtask uses $\min$ scoring (that is, if you get even one test wrong, you get $0$ points for the last $50$ points).

Translated by ChatGPT 5