Tesseract

Time limit2sMemory limit1024 MB

Summary

Count the palindromic substrings [l, r] of a lowercase string that have some strictly larger segment which is not a palindrome.

Level: Medium5 of 10
Topics: String, String matching
Solved: No attempts yet

Statement

Loki attacked Earth with the Tesseract, which he took from Asgard. Knowing its value, he wants to protect it so that only he can use it, so he plans to change its internal structure in a way that only he knows how to restore. Inside the Tesseract is a chain of small cubes. Some of them look almost identical, and Loki intends to use this. Hoping that people will not notice, he makes two changes, and after each change the artifact must look the same as before. The chain has $n$ cubes. Loki takes a contiguous segment of the chain, removes it, reverses it, and puts it back in place. He chooses the segment so that the chain looks unchanged from the outside. Then he repeats the same operation with another segment that contains the first one and does not coincide with it. After these two operations the chain differs from the original, and the artifact is damaged. To estimate the risk of being caught, Loki wants to know how many different segments he could choose for the first operation.

Input

The only line contains a string of lowercase Latin letters with length at most $100{,}000$ .

Output

Print a single integer, the number of different first operations Loki can make.

Examples1

Example 1
Input
```
aabaa
```
Expected output
```
8
```