Counting Excellent Splits

We call a split of a string into the form $\mathrm{AABB}$ excellent if the string can be partitioned into four contiguous parts as [ X = A + A + B + B, ] where $A$ and $B$ are arbitrary nonempty strings. For example, consider the string aabaabaa. It can be split in an excellent way by taking [ A = \mathtt{aab},\quad B = \mathtt{a}, ] since [ \mathtt{aab} + \mathtt{aab} + \mathtt{a} + \mathtt{a} = \mathtt{aabaabaa}. ] Note that another excellent split for the same string is obtained by taking [ A = \mathtt{a},\quad B = \mathtt{baa}. ] A string may not have any excellent split, or it may have more than one. Given a string $S$ of length $n$, your task is to count the total number of excellent splits over all substrings (continuous segments) of $S$.

Important notes:

1. Two occurrences of the same substring (at different positions) are considered distinct, and their excellent splits are all counted.
2. In a split, it is allowed that $A = B$. For example, cccc has an excellent split with $A = B = \mathtt{c}$.
3. The string $S$ itself is also considered as one of its substrings.

inputFormat

The input consists of a single line containing the string $S$.

$S$ consists of only lowercase English letters.

outputFormat

Output a single integer: the total number of excellent splits among all substrings of $S$.

sample

aaaa

1