Problem Description

Given a string $ S $ consisting of lowercase English letters, solve the following problem for all contiguous substrings of $ S $, which number $ |S|(|S|+1)/2 $. Compute the sum of the values of the solutions.

Problem: Given a string $ T $ consisting of lowercase English letters, determine the minimum length of a string that can be obtained by repeating the following operation any number of times:

• Choose any prefix of $ T $ that is a palindrome of odd length (let's say $ 2k+1 $ characters). Delete the first $ k $ characters of $ T $.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

abab

Sample Output #1

16

Sample Input #2

abacaba

Sample Output #2

67

Sample Input #3

tabatadebatabata

Sample Output #3

739

Notes/Hints

Constraints

• $1 \leq |S| \leq 10^6$
• $ S $ consists of lowercase English letters

Sample Explanation 1

When $ T $ is a or b, the answer is $ 1 $. When $ T $ is ab or ba, the answer is $ 2 $. When $ T $ is aba or bab, the optimal operation is to choose $ k=1 $ once, resulting in an answer of $ 2 $. When $ T $ is abab, the optimal operations are to choose $ k=1 $ twice, resulting in an answer of $ 2 $. Therefore, the total answer is $1 \times 4 + 2 \times 3 + 2 \times 2 + 2 \times 1 = 16$.

见题面 Input 部分

见题面 Output 部分