Problem Background

P-Bro has started learning about strings!

Problem Description

P-Bro has learned a new method for string manipulation—rotation.

"Rotation" is an operation where the last character of the original string is removed and added to the front, resulting in a new string.

P-Bro can perform the "rotation" operation infinitely many times to maximize the number of distinct palindromic substrings in the new string.

Two palindromic substrings are considered distinct if they have different lengths or if at least one character at the same position is different.

Given a string \( S \), you are to help P-Bro achieve his goal (as highlighted above) by performing the "rotation" operation and output the number of distinct palindromic substrings in the new string.

Input Format

The input consists of a single line representing the string \( S \), which contains only lowercase English letters.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

ioimoio

Sample Output #1

7

Sample Input #2

fcfcfcfcfczxqprvvlpstpasxvpyyhaejxehdlhckmwmibsjwqbmfzlwpjqjghmlxunefabkpryqxbkqridpqrzemvfcfcfcfcfc

Sample Output #2

47

Notes

Let \( n \) be the length of string \( S \).

• For the first 20% of the data, \( n \le 100 \).
• For the first 40% of the data, \( n \le 2000 \).
• For another 10% of the data, it is guaranteed that no rotation is needed to get the correct answer.
• For 100% of the data, \( n \le 1.5 \times 10^6 \).

Additionally, for the last 50% of the data, the length of the non-random part of string \( S \) does not exceed 5000.

Note: This problem uses a subtask scoring method. The first 50% of the data is subtask #1, which scores by summation (you can consider it as the traditional scoring method). The last 50% of the data is subtask #2, which scores by taking the minimum (i.e., if one point is wrong, the last 50 points are lost).

见题面 Input 部分

见题面 Output 部分