Problem H
Help Eevee Pls Eh

Eevee recently learned that its name is a palindrome! This means that it reads the same forward and backward.

However, Eevee is sad to discover that not many words are palindromes. One day, Eevee was visited by a friend. Upon hearing the friend’s name, Eevee became curious.

Eevee wondered how many different ways there are to remove a single character from the friend’s name so that the remaining characters, when concatenated, form a palindrome.

For example, in eevaee, removing either v or a is valid, but removing any of the e’s is not.

We define a palindrome as the following: Given a string $S = s_1s_2\dots s_n$, we pair $(s_1, s_n)$, $(s_2, s_{n-1})$, $\dots $, $(s_{\lfloor \frac{n}{2}\rfloor }, s_{\lfloor \frac{n}{2}\rfloor + 1})$. $S$ is a palindrome if and only if in all of these $\lfloor \frac{n}{2}\rfloor $ pairs the characters in the pairs are identical.

Input

The first line of input contains an single string $S$ ($2 \leq |S| \leq 10^6$), the friend’s name consisting of lowercase English letters a to z.

Output

Output a single integer representing the number of ways to remove a character from $S$ such that it becomes a palindrome.

Sample Explanation

For the string eevaee$ = s_1s_2s_3s_4s_5s_6$, if we simulate removing each character:

Removing $s_1$: We have pairs $(s_2, s_6), (s_3, s_5)$, $1$ of these pairs are identical.

Removing $s_2$: We have pairs $(s_1, s_6), (s_3, s_5)$, $1$ of these pairs are identical.

Removing $s_3$: We have pairs $(s_1, s_6), (s_2, s_5)$, $2$ of these pairs are identical.

Removing $s_4$: We have pairs $(s_1, s_6), (s_2, s_5)$, $2$ of these pairs are identical.

Removing $s_5$: We have pairs $(s_1, s_6), (s_2, s_4)$, $1$ of these pairs are identical.

Removing $s_6$: We have pairs $(s_1, s_5), (s_2, s_4)$, $1$ of these pairs are identical.

Thus, only for 2 of the characters is the number of valid pairs $\lfloor \frac{5}{2}\rfloor = 2$, thus the answer is $2$.

eevaee

2

helpeeveeplseh

1