Given a string $s$ consisting of lowercase letters. Let its length be denoted by $|s|$, and let its reverse be denoted by $s^R$ (the string obtained by reversing the order of characters of $s$). Also, we use $\operatorname{prefix}(s, i)$ to denote the substring consisting of the first $i$ characters of $s$, and $\operatorname{suffix}(s, i)$ to denote the substring consisting of the last $i$ characters of $s$.

Based on this, we define the $\operatorname{Porder}$ value of a string $s$ as the largest integer $i$ satisfying the following condition: $$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$ where $0 \le i \le |s|$. In particular, if no positive integer satisfies the above condition, then the $\operatorname{Porder}$ value is $0$.

A substring of $s$ is defined as a contiguous segment of characters from the $l$-th character to the $r$-th character, where indices start from $1$ and satisfy $1 \le l \le r \le |s|$.

Now, please compute the sum of the $\operatorname{Porder}$ values of all substrings of the string $s$.

Input

The input consists of a single line containing a string $s$ $(1 \le |s| \le 10^5)$. It is guaranteed that the string contains only lowercase letters.

Output

Output a single integer, representing the sum of the $\operatorname{Porder}$ values of all substrings of $s$.

Examples

Input 1

aa

Output 1

4

Input 2

abcdba

Output 2

9

Note

Taking Example 2 as an example:

• The substrings with $\operatorname{Porder}$ value $2$ are: abcdba ($1$ in total).
• The substrings with $\operatorname{Porder}$ value $1$ are: bcdb, and all substrings of length $1$ ($7$ in total).
• All remaining substrings have $\operatorname{Porder}$ value $0$.

Therefore, the sum of the $\operatorname{Porder}$ values over all substrings is $1 \times 2 + 7 \times 1 + 0 = 9$.